常用正则表达式
1.数字
- nat = [0-9]+
- signalnat = (+|-)?nat
- number = signalnat(“.”nat)?(E signalnat)?
2.保留字、Id
- reserved = if|while|do|…
- letter = [a-z A-z]
- digit = [0-9]
- identifier = letter(letter|digit)*
根据REX构建NFA
DFA 与 NFA 的转换
从 NFA 的开始符号S开始，求它的ε闭包，然后再看这个闭包可以到达的位置，最后把这些闭包作为一个状态。
EBNF 扩充的巴科斯范式
元语言：→、::=、|
- 用{a}表示闭包运算a*
- 用{a}0n表示可重复0次至N次
- 用[a]表示{a}01，即a|ε
二义文法定义
an ambiguous grammar: a grammar that generates a string with two distinct parse trees is called an ambiguous grammar.
一种生成具有两个不同解析树的字符串的语法称为二义语法。
LL(1)文法：消除左递归
1.直接左递归
P -> Pa|b
直接左递归变右递归：
P -> bP'
P' -> aP' | ε
2.间接左递归
条件：不含 ε 的产生式、不含回路。
*按某种顺序排列 P1,P2,…,PN。
*把Pi的规则改成 Pi->a...|Pi+1...|.... （Pi不含i以前的项）
*把间接左递归中的引用替换为它的定义。
*删除永远无法到达的规则。
LL(1)文法：消除回溯
A -> cb1|cb2|cb3 ...
*提取左公共因子
A -> cA'
A' -> b1|b2|b3 ...
First 集合
一个串能推出的任意串，排在开头位置的终结符。
*如果x能推出ε，则ε也处于First(x)。
Follow 集合
在某个句型里，能跟在这个串后面的终结符。
*对开始符号S，把$置于Follow(S)中。
*若A->aBb， 则把First(b)中非ε元素加入Follow(B)。
*若A->aB，则把Follow(A)加至Follow(B)中。
LL(1)文法的判定
1.文法不含左递归
2.对每一个非终结符A的产生式候选首符集两两不相交。
即 First(ai)∩First(aj) = ∅
3.对文法的每个终结符A，若它存在某个候选首符集包含ε，则
First(ai)∩Follow(A) = ∅
LL(1)分析法
| Step | Stack | Input | Action |
| number | $起始符号 | 堆栈内容$ | match|
使用产生式匹配| 对于Stack=Input=$时为Accept |
LL(1)分析表
| M[A,b] | 终结符 |
| 非终结符 |
*A->a 放在A行First(a)列
*A->ε 放在A行Follow(A)列
活前缀
Determining the next handle in a parse is the main task of a shift-reduce parser.
The sequence of symbols on the parsing stack is called a viable prefix of the right sentential form .
LR(0)分析法
*在产生式的基础上增加一些位置信息组成 Item.
| Step | Parsing stack | Input | Action |
| number | $ | 输入内容 $ | Shift|
Reduce| 对于Parsing stack为S时Accept |
LR(0)分析表
| State | Input | Goto |
| number | s+state|
r+产生式编号 |
state |
Input下有多种终结符，Go下有多种非终结符。Goto表示当Parsing栈顶为非终结符时跳转到哪个状态。
SLR(1)文法判定
1.无移进归约冲突。
2.有两种归约结果如A->a·与B->b·，根据Follow集合决定归约哪一个。
LR(1)文法
*把向前看的状态也放到Item里。
[A->α·β,a]
[S'->·S,$]
1.不存在移入、归约冲突。
2.不存在归约、归约冲突。
LALR(1)
合并向前看的符号。
*不可能有移入和归约的冲突。
*如果一个语法是SLR(1)的，那么它是LALR(1)的。
生成方法：从LR(0)开始增加向前看的符号。（**）
错误分析
LR(1)发现错误早于LALR(1)和SLR(1)。
如果存在错误情况，就找Goto的情况，帮助完成这个分析。
综合属性
自下而上传递信息。
语法规则：根据右边符号计算左部被定义符号的综合属性。
语法树：根据子节点的属性和父节点自身的属性计算父节点的综合属性。
继承属性
自上而下传递信息。
语法规则：根据右部候选式中的符号属性和左部被定义符号的属性计算右部候选式中的符号的继承属性。
语法树：根据父节点和兄弟节点的属性计算子节点的继承属性。
0 条评论