语法范式
语法范式
上下文无关的组成部分:
- 终结符号
- 非终结符号
- 一个开始符号
- 一组产生式
例如,下面数学表达式:
- 终结符号(词法单元)是组成串的基本符号,例如上面的
+
,-
。 - 非终结符号是表示串的集合的语法变量,例如上面的term和factor。非终结符号表示的串集合用于定义由文法生成的语言。
左结合 & 右结合
$expr \to term \space opeartor \space expr \space|\space term$
$E \to T \space \lbrack \space op \lbrack \space T \space op \space T \rbrack \rbrack$
上述的操作符operator是右结合的(优先结合右边的部分)。
$expr \to expr \space opeartor \space term \space|\space term$
$E \to \lbrack \lbrack T \space op \space T \rbrack op \space T \rbrack \space T$
上述的操作符operator是左结合的(优先结合左边的部分)。
左递归的消除
注意,下面的文法是左递归的:
$expr \to expr+term$
这种文法是不能直接用于自顶向下分析的。expr -> expr(-> expr(…) + term) +term。需要使用递归消除技术,来消除左递归。
左递归分为两种:
- 直接左递归: $P \to Pa$
- 间接左递归: $P \to Aa ,A \to …\to PB$
对于直接左递归,一般形式是$P \to PX | Y$.
- $P \to YP’$
- $P’ \to XP’| \varepsilon$
P 实际上是 Y 开头的后面若干个X
对于间接左递归:
- 若消除过程中出现了直接左递归,就按照直接左递归的方法,来消除
- 若产生式右部最左的符号是非终结符,且这个非终结符序号大于等于左部非终结符,则暂不处理(后面会处理到)
- 若序号小于左部的非终结符,则用之前非终结符序号对应的产生式右部来替换
1 | // 1.把文法G的所有非终结符按任意顺序排列,并编号 |
例如存在如下文法G,要消除左递归
1 | 1. S → Qc | c |
- 把文法G的所有非终结符按任意顺序排列,并编号
R、Q、S
- 按上面的排列顺序,对这些非终结符进行遍历
- 将当前处理的非终结符中的序号小于等于它的非终结符按规则3)进行替换(序号大于的按规则2)处理)
1 | R: |
- 消除i序号的非终结符的直接左递归(如果存在的话)
1 | S → Sabc |abc | bc | c |
- 删除其中不可达的非终结符,这里就是Q、R了
BNF
在BNF表示法中,实体按照以下格式以其他实体的形式定义:
1 | <a> :: = <b> <c> |
这种表示法意味着实体<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 = ; |
描述自身
1 | letter = "A" | "B" | "C" | "D" | "E" | "F" | "G" |
Pascal风格的例子
1 | (* a simple program syntax in EBNF − Wikipedia *) |
代码示例
1 | PROGRAM DEMO1 |
ABNF
ABNF 结构
1 | rule = definition ; comment CR LF |
定义
规则 | 定义 | 含义 |
---|---|---|
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 | postal-address = name-part street zip-part |