我们之前意见写好了自动机,接下来用自动机来构建语法分析表。
语法分析表由两部分组成,一个语法分析动作函数ACTION和一个转换函数GOTO
- ACTION函数有两个参数:一个是状态i,另一个是终结符号a(或是输入标记符号$),ACTION[i,a]有四种形式:
- 移入j,j是一个状态
- 归约A->β
- 接受
- 报错
2.我们把定义在项集上的GOTO函数拓展为定义在状态集上的函数:如果GOTO[Ii,A] = Ii,那么GOTO也把状态i和一个非终结符号A映射到状态j。
构建表示,我们约定:
- si表示移入并将状态i压栈
- rj表示按照编号j的产生式归约
- acc表示接受
- 空白表示报错
示例文法:
E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id
构建自动机:
构建语法分析表:
构建算法:
假设已构造出LR(0)项目集规范族为:C={I0,I1, … , In},其中Ik为项目集的名字,k为状态名,令包含S′→·S项目的集合Ik的下标k为分析器的初始状态。那么分析表的ACTION表和GOTO表构造步骤为:
① 若项目A→α·aβ属于Ik且转换函数GO(Ik,a)= Ij,当a为终结符时则置ACTION[k,a]为Sj。
② 若项目A→α· 属于Ik,则对任何终结符a 和’#'号置ACTION[k,a]和ACTION[k,#]为”rj”,j为在文法G′中某产生式A→α的序号。
③ 若GO(Ik,A)=Ij,则置GOTO[k,A]为”j”,其中A为非终结符。
④ 若项目S′→S·属于Ik,则置ACTION[k,#]为”acc”,表示接受。
⑤ 凡不能用上述方法填入的分析表的元素,均应填上”报错标志”。为了表的清晰我们仅用空白表示错误标志。