算符优先表:行与列都是终结符
A->aB B->bc 则 a<b
A->aBd B->bc 则c>d
firstvt定义< lastvt定义>
注意算符优先表是根据产生式进行的
每次规约都包括至少一个终结符在内的内容
规范分析是基于句柄的。
注意,如果下推栈中是then N 输入串是else,是用then与else比较,而不是用N与else比较
之所以都归结为N是因为不需要了解终结符的类型,只要知道都能规约为N就可以了
第33讲习题课
LR分析法:
LR(0)不需要向前看
第36章 LR分析
LR主要问题就是实现LR分析表
如果在action表中,一直没有对应到s移入跳转状态,而一直是r规约,那么就一直规约,直到进入s状态
找到活前缀,就是找到了句柄。
手动构造十分困难
用于确定状态,项目集
第38讲
如何构造项目集族
确定和非确定的不同在于确定没有空串
根据规约出来的不同的非终结符或者不同的输入串进行移进或者规约
遇到E的情况是规约的情况,否则是不会遇到非终结符的。
6.7.8.9.10.11状态都是可以规约的相应的方框内部的数字是状态,而后面的产生式,则是根据该产生式,可以将这个产生式右部进行规约,即如果栈内从栈底到栈顶如果依次是abcd,则首先d规约成B,B和c规约成B,B和b规约成E,E与a规约成E。
只有go表中是遇到非终结符时,跳转到状态的。
LR0仅仅是根据栈内的进行分析,不存在预判之类的,因此能力比较弱。
按照4号产生式进行规约,即10号状态无论遇到什么鬼,都用r4进行规约,规约成A
LR0只考虑栈内的符号是否构成句柄,而不管读头的符号。
第39讲
消除规约规约冲突,即如果栈中有阿发,究竟规约成A还是B。
这么做的前提是A B的follow集合不同,通过前看符号,解决规约规约冲突。
与LL0分析表的不同在于第二条,LL0要求的是对a要求是属于follow集合的。
也就是对A规约增加了更加严格的限制
实际上就是I1, I2, I3会因为究竟是要移进字符还是规约而存在冲突
当仅仅考虑栈里信息和读头的信息可能仍然无法有效规约。
第40讲
遇到=号时,R的follow集合中也有=,这就不知道究竟是移进还是规约了。(没懂啊!!!)
我感觉可能是,如果在2状态中,如果遇到了=号,究竟是将L规约为R,还是继续将=R读完,
L=R一起规约成S
如果遇到=号,将*R规约成L,即只有使用2进行推导时,才能接受=;否则R的后面不接受等于号
也就是说=与2号产生式相关,虽然R的follow集合中有等于号,但不是所有的R遇到等于号都可以
规约,而只是使用S产生式推导才行。
重点在于b还没有入栈,a是展望的
如果想把e规约成A,那么一定要展望符号是d的时候(这就是LR0遇到的移进和规约分不清的问题)
能follow c的情况只有是3号产生式产生时,能follow d的情况只能是2号产生式时。
如果栈内时bA,那么展望一定不能是d,如果展望的是d,那么一定不要规约;
相反,要使用移进即移入后使用5号产生式规约。
对于LR0中的某个项目集加上展望符号,构成新的项目集合。
栈外是非终结符时,就要进行展望
查找规范句型中每一个句柄后面的符号,进行识别。
只有遇到规范句型的展望符号才规约
(
LR0 任何符号
SLR follow集合中的符号
)
即除了展望符号不同,其余都相同
LALR解决了LR1分析表比较大的问题,规模与LR0相同。