LALR(1)实例

假设有如下文法

S ::= E

E ::= E - E
E ::= E + E
E ::= int

我们首先列出第一个产生式的第一个项目 state 0

state 0:
S ::= .E

由于右部 . 后面是非终结符,所以还需补上 等价项目

E ::= .E - E
E ::= .E + E
E ::= .int

在 state 0 基础上,如果遇到 E,移入并进入 state 1

state 1:
S ::= E.

E ::= E .- E
E ::= E .+ E

在状态0基础上,如果遇到 int,移入并进入 state 2

state 2:
E ::= int.

在 state 2 基础上,int 需要归约为 E 进入 state 1

在 state 1 基础上如果遇到 $ 空串,归约为 S 进入 state 0 即接收成功

在 state 1 基础上如果遇到 - ,移入并进入state 3

state 3:
E ::= E - .E

E ::= .E - E
E ::= .E + E
E ::= .int

在 state 1 基础上如果遇到 +,移入并进入 state 4

state 4:
E ::= E + .E

E ::= .E - E
E ::= .E + E
E ::= .int

在 state 3 基础上如果遇到 E 则移入并进入 state 5

state 5:
E ::= E + E.

E ::= E .- E
E ::= E .+ E

在 state 3 基础上如果遇到 int 则移入并进入 state 2

在 state 4 基础上如果遇到 E 则移入并进入 state 6

state 6:
E ::= E + E.

E ::= E .- E
E ::= E .+ E

在 state 4 基础上如果遇到 int 则移入并进入 state 2

在 state 5 基础上遇到任何符号都归约并进入 state 3

在 state 6 基础上遇到任何符号都归约并进入 state 4  

大致如下图所示:



参考书本:

    LEMON 语法分析生成器


参考链接:

    sqlite 源码中的 lemon.c



上一篇: 编译原理学习笔记
下一篇: 无
作者邮箱: 203328517@qq.com