语法范式
上下文无关的组成部分:
例如,下面数学表达式:
e x p r → e x p r + t e r m expr \to expr+term
e x p r → e x p r + t e r m
e x p r → e x p r − t e r m expr \to expr-term
e x p r → e x p r − t e r m
e x p r → t e r m expr \to term
e x p r → t e r m
t e r m → t e r m ∗ f a c t o r term \to term * factor
t e r m → t e r m ∗ f a c t o r
t e r m → t e r m / f a c t o r term \to term/factor
t e r m → t e r m / f a c t o r
t e r m → f a c t o r term \to factor
t e r m → f a c t o r
f a c t o r → ( e x p r ) factor \to (expr)
f a c t o r → ( e x p r )
f a c t o r → i d factor \to id
f a c t o r → i d
终结符号(词法单元)是组成串的基本符号,例如上面的 +
,-
。
非终结符号是表示串的集合的语法变量,例如上面的term和factor。非终结符号表示的串集合用于定义由文法生成的语言。
左结合 & 右结合
e x p r → t e r m o p e a r t o r e x p r ∣ t e r m expr \to term \space opeartor \space expr \space|\space term e x p r → t e r m o p e a r t o r e x p r ∣ t e r m
E → T [ o p [ T o p T ] ] E \to T \space \lbrack \space op \lbrack \space T \space op \space T \rbrack \rbrack E → T [ o p [ T o p T ] ]
上述的操作符operator是右结合的(优先结合右边的部分)。
e x p r → e x p r o p e a r t o r t e r m ∣ t e r m expr \to expr \space opeartor \space term \space|\space term e x p r → e x p r o p e a r t o r t e r m ∣ t e r m
E → [ [ T o p T ] o p T ] T E \to \lbrack \lbrack T \space op \space T \rbrack op \space T \rbrack \space T E → [ [ T o p T ] o p T ] T
上述的操作符operator是左结合的(优先结合左边的部分)。
左递归的消除
注意,下面的文法是左递归的:
e x p r → e x p r + t e r m expr \to expr+term e x p r → e x p r + t e r m
这种文法是不能直接用于自顶向下分析的。expr -> expr(-> expr(…) + term) +term。需要使用递归消除技术,来消除左递归。
左递归分为两种:
直接左递归: P → P a P \to Pa P → P a
间接左递归: P → A a , A → . . . → P B P \to Aa ,A \to ...\to PB P → A a , A → . . . → P B
对于直接左递归,一般形式是 P → P X ∣ Y P \to PX | Y P → P X ∣ Y .
P → Y P ′ P \to YP' P → Y P ′
P ′ → X P ′ ∣ ε P' \to XP'| \varepsilon P ′ → X P ′ ∣ ε
P 实际上是 Y 开头的后面若干个X
对于间接左递归:
若消除过程中出现了直接左递归,就按照直接左递归的方法,来消除
若产生式右部最左的符号是非终结符,且这个非终结符序号大于等于左部非终结符,则暂不处理(后面会处理到)
若序号小于左部的非终结符,则用之前非终结符序号对应的产生式右部来替换
1 2 3 4 5 6 7 8 9 10 11 12 13 [P1,P2,……,Pn] for (int i = 1 ; i <= n; ++i) { for (int j = 1 ; i <= i - 1 ; ++j) { } 1 ) }
例如存在如下文法G,要消除左递归
1 2 3 1. S → Qc | c 2. Q → Rb | b 3. R → Sa | a
把文法G的所有非终结符按任意顺序排列,并编号R、Q、S
按上面的排列顺序,对这些非终结符进行遍历
将当前处理的非终结符中的序号小于等于它的非终结符按规则3)进行替换(序号大于的按规则2)处理)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 R: R的右部中的非终结符有S; S的下标大于R,可以暂时不处理; 所以此时R为:R → Sa | a ---------------------------------------------- Q: Q的右部中的非终结符有R; R的下标小于Q,将R的右部替换进来; 所以此时Q改写为:Q → Sab | ab | b; S的下标大于Q,可以暂时不处理; 所以此时Q为:Q → Sab | ab | b; ----------------------------------------- S: S的右部中的非终结符有Q; Q的下标小于S,将Q的右部替换进来; 所以此时S改写为:S → Sabc |abc | bc | c S的下标等于S,可以暂时不处理; 所以此时S为:S → Sabc |abc | bc | c
消除i序号的非终结符的直接左递归(如果存在的话)
1 2 3 4 5 S → Sabc |abc | bc | c ∴ X = abc,Y = abc | bc | c ∴ 直接消除左递归的结果是: S → abcS' | bcS' | cS' S' → abcS' | ε
删除其中不可达的非终结符,这里就是Q、R了
BNF
在BNF表示法中,实体按照以下格式以其他实体的形式定义:
这种表示法意味着实体<a>
由实体<b>
后跟实体<c>
组成。由<和>括起来的实体在语法的其他地方进一步定义。<和>之间没有出现的任何东西都代表着它自己。
如果一个实体可以由多个序列定义,则序列由垂直线分隔:
1 <a> :: = <b> <c> | <d> "BEGIN"
在此示例中,实体<a>
由<b>
后跟实体<c>
或<d>
后跟字符BEGIN
组成。双引号包围的代表字符。
1 <personal-part> ::= <initial> "." | <first-name>
正在定义的实体也可以出现在定义中,在这种情况下,定义是递归的。例如:
1 <a> :: = <b> <c> | <d> "BEGIN"| <a> <e>
一个BNF 的分析例子: Algol-BNF
EBNF
EBNF是一种表达形式语言语法的代码。EBNF由终端符号和非终端生成规则组成,这些规则是管理终端符号如何组合成合法序列的限制。
用法
符号
定义
=
级联,连接符号
,
终止
;
OR
|
可选的
[ … ]
重复
{ … }
分组
( … )
字符串,内部不可出现"
" … "
字符串,,内部不可出现'
’ … ’
注释
(* … *)
特殊序列
? … ?
除了
-
EBNF 文法部分的特殊序列,它是在问号包围内的任意文本,其解释超出了 EBNF 标准的范围。例如,空格字符可以用如下规则定义:
1 space = ? US-ASCII character 32 ? ;
描述自身
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 letter = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" ; character = letter | digit | symbol | "_" ;identifier = letter , { letter | digit | "_" } ;terminal = "'" , character , { character } , "'" | '"' , character , { character } , '"' ; lhs = identifier ;rhs = identifier | terminal | "[" , rhs , "]" | "{" , rhs , "}" | "(" , rhs , ")" | rhs , "|" , rhs | rhs , "," , rhs ; rule = lhs , "=" , rhs , ";" ;grammar = { rule } ;
Pascal风格的例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 program = 'PROGRAM' , white space, identifier, white space, 'BEGIN' , white space, { assignment, ";" , white space }, 'END.' ; identifier = alphabetic character, { alphabetic character | digit } ;number = [ "-" ], digit, { digit } ;string = '"' , { all characters - '"' }, '"' ;assignment = identifier , ":=" , ( number | identifier | string ) ;alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;white space = ? white space characters ? ;all characters = ? all visible characters ? ;
代码示例
1 2 3 4 5 6 7 8 9 10 PROGRAM DEMO1 BEGIN A:=3 ; B:=45 ; H:=-100023 ; C:=A; D123:=B34A; BABOON:=GIRAFFE; TEXT:="Hello world!"; END .
ABNF
ABNF 结构
定义
规则
定义
含义
ALPHA
%x41-5A / %x61-7A
大写和小写ASCII字母(A-Z,a-z)
DIGIT
%x30-39
十进制数字(0-9)
HEXDIG
DIGIT / “A” / “B” / “C” / “D” / “E” / “F”
十六进制数字(0-9,A-F)
DQUOTE
%x22
双引号
SP
%x20
空格Space
HTAB
%x09
tab
WSP
SP / HTAB
Space and horizontal tab
LWSP
*(WSP / CRLF WSP)
Linear white space (past newline)
VCHAR
%x21-7E
可见字符
CHAR
%x01-7F
任何ASCII字符,不包括NUL
OCTET
%x00-FF
8 bits of data
CTL
%x00-1F / %x7F
Controls
CR
%x0D
回车
LF
%x0A
换行
CRLF
CR LF
标准换行
BIT
“0” / “1”
二进制数字
操作符
用法
例子
注释
;comment
从;
到行尾表示注释的开始和结束
级联,连接
Rule1 Rule2
表示Rule1 Rule2的连接
终止
;
OR
/
值范围
%c##-##
,例如 OCTAL = %x30-37
分组
( … )
可变重复
<a>*<b>element
表示元素的重复。可选项<a>
提供要包含的最少元素数(默认值为0)。可选项<b>
给出了要包含的最大元素数(默认值为无穷大).*element
:零个或更多的元件,*1element
:零个或一个元件,1*element
:一个或多个元件,2*3element
:两个或三个元素
具体重复
<a>element
表示明确的元素数量,,相当于<a>*<a>element
,2DIGIT:两个数字
可选顺序
[Rule]
表示可选元素
字符串,内部不可出现"
" … "
字符串,,内部不可出现'
’ … ’
除了
-
以下运算符具有从最严格的绑定到最松散绑定的给定优先级:
字符串
注释
值范围
重复
分组,可选
级联
替代
例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 postal-address = name-part street zip-partname-part = *(personal-part SP ) last-name [SP suffix] CRLF name-part =/ personal-part CRLF personal-part = first-name / (initial "." )first-name = *ALPHA initial = ALPHA last-name = *ALPHA suffix = ("Jr." / "Sr." / 1 *("I" / "V" / "X" ))street = [apt SP ] house-num SP street-name CRLF apt = 1 *4 DIGIT house-num = 1 *8 (DIGIT / ALPHA )street-name = 1 *VCHAR zip-part = town-name "," SP state 1 *2 SP zip-code CRLF town-name = 1 *(ALPHA / SP )state = 2 ALPHA zip-code = 5 DIGIT ["-" 4 DIGIT ]
参考