编译器之 Lexcial Specifications

Lexical Specifications

Keyword: "if" "else" or "then" or ...
- regular expression: "i""f" + "e""l""s""e"
- 简化："if" + "else" + "then" + ...
Integer: non empty string of digits
- regular expression:
- digit = '0' + '1' + '2' + '3' + '4' + '5' + '6' + '7' +'8' + '9'
- digit = [0-9]
- digits = digit digit*
- 简化：digits = digit+
Identifier: strings of letters or digits, starting with a letter
- regular expression:
- letter = 'a' + 'b' + 'c' + ... + 'A' + 'B' + 'C' + ...
- 简化：letter = [a-zA-Z]
- Identifier = letter (letter + digit)*
Whitespace: a non empty sequence of blanks, newlines, and tabs
- regular expression:
- (' ' + '\n' + '\t')+
anyone@cs.stanford.edu
- letter+ '@' letter+ '.' letter+ '.' letter+
Pascal
- digit = [0-9]
- digits = digit+
- opt_fraction = ('.' digits) + ε
- opt_exponent = ('E' ('+' + '-' + ε) digits) + ε
- num = digits opt_fraction opt_exponent
- 优化：
- opt_fraction = ('.' digits)?
- opt_exponent = ('E' ('+' + '-')? digits)?
Regular expressions describe many useful languages
- email
- phone numbers
- file names
- ...
Regular languages are a language specification
- Still need an implementation
Given a string s and a rexp R, is s ∈ L(R) ?

有趣，使用正则语言描述词法规范，自然催生出 ? + [0-9] 这种简写模式。

至此，更加理解正则表达式的形式定义：

The empty language Ø is a regular language.
For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
If A is a regular language, A* (Kleene star) is a regular language. Due to this, the empty string language {ε} is also regular.
If A and B are regular languages, then A ∪ B (union) and A • B (concatenation) are regular languages.
No other languages over Σ are regular.

要素：

简写模式：

xxleyi / learning_list