bison解析中lookahead前瞻工作原理

2023-01-13 12:16:05 浏览数 (2)

https://www.gnu.org/software/bison/manual/bison.html#Algorithm

1 lookahead token

学习yacc后一直有一个疑问，reduce到底什么时候发生？ 遇到匹配的规则立即执行reduce吗？还是在等一等看看后面的token，可能匹配上其他的规则？

bison行为：

  • bison解析器并不是遇到栈顶的一组token匹配上规则后，立即执行recude。因为这种简单的策略不能满足一些复杂语言的需要。
  • bison解析器在发现一次匹配后，会继续向前看一个lookahead，再决定做什么。

具体步骤：

  1. 当读到一个token时，并不立即shift进入堆栈，而是把他当成lookahead token（不入栈）。
  2. 然后解析器就可以执行栈上的匹配动作了，匹配上就可以reduce。lookahead token放在一边。
  3. 当没有token能进行reduce后，再把lookahead token shift入栈。

上面的步骤2并不是匹配上的都能reduce，lookahead token会影响一些规则，使其延迟reduce。

1.1 lookahead token案例分析

  • 这是一个有相互依赖关系的语法树。term可以reduce为expr；expr加括号可以reduce为term。
  • !是后缀运算符，表示阶乘。
  • 语法支持括号分组。
代码语言：javascript复制
expr:
  term ' ' expr
| term
;

term:
  '(' expr ')'
| term '!'
| "number"
;

当1 2进入语法树时，如果不向前看一个token，会发生的问题：

代码语言：javascript复制
         1   2 )
            /
          1   2 reduce为：expr     ')'
                                  /
                            expr 和 右括号reduce为term

如果1 2后面跟的是!，上面的1 2已经被reduce为expr，叹号肯定是无法匹配上了。

所以要reduce'1 2'时，必须向前看一个，再决定1 2要不要reduce。

  • 如果lookahead=)，可以直接reduce。
  • 如果lookahead=!，需要延迟reduce，什么也不做。

1.2 lookahead读取方法

  • lookahead token
    • yychar
  • lookahead token值
    • yylval
  • lookahead token位置
    • yylloc

2 Shift/Reduce冲突

实例：其中"if"、“then”、"else"终结符

代码语言：javascript复制
if_stmt:
  "if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;

假设当前"if"、“then"都已经在解析栈中，lookahead是"then”。

  • 选择1：当前解析栈按规则1规约。
  • 选择2：lookahead继续shift入栈，按规则2规约。

现在发生了shift/reduce冲突。Bison会通过选择shift来解决这些冲突（除非运算符优先级声明）。

3.1 悬挂冲突

为了解其中的原因，下面与其他选择进行对比：

正例：如果bison更偏向于shift “else”，下面语句1就等价与语句2，符合预期。

代码语言：javascript复制
-- 语句1
if x then 
  if y then win; 
  else lose;

-- 语句2：else和里面的If结合，符合预期
if x then do; 
  if y then win; 
  else lose; end;

反例：如果bison更偏向于reduce，下面语句1就等价与语句2，不符合预期。

能shift也能recude得时候，先recude了，

代码语言：javascript复制
-- 语句1
if x then 
  if y then win;    -- 栈：if then if then(lookahead=else)，看到后一个if then直接recude了。
  else lose;        -- 剩下一个else，只能和外面的if一起recude了。

-- 语句2：else和外面的if结合，不符合预期。
if x then do; 
  if y then win; end; 
else lose;          -- 结果就是else给外面的if了，但预期是需要和里面的if结合。

这就是经典的“dangling else”冲突，悬挂的else。

文件

代码语言：javascript复制
%%
stmt:
  expr
| if_stmt
;

if_stmt:
  "if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;

expr:
  "identifier"
;

bison --report=counterexamples if.y output文件

代码语言：javascript复制
State 9

    3 if_stmt: "if" expr "then" stmt •
    4        | "if" expr "then" stmt • "else" stmt

    "else"  shift, and go to state 10
后面挂了一个else，是要等else进来shift，还是
    "else"    [reduce using rule 3 (if_stmt)]
直接reduce掉前面的if then？
    $default  reduce using rule 3 (if_stmt)

    shift/reduce conflict on t0ken "else":
        3 if_stmt: "if" expr "then" stmt •
        4 if_stmt: "if" expr "then" stmt • "else" stmt
      Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
      Shift derivation
        if_stmt
        ↳ 3: "if" expr "then" stmt
                              ↳ 2: if_stmt
                                   ↳ 4: "if" expr "then" stmt • "else" stmt
      Reduce derivation
        if_stmt
        ↳ 4: "if" expr "then" stmt                              "else" stmt
                              ↳ 2: if_stmt
                                   ↳ 3: "if" expr "then" stmt •

3 解析器状态

  • yyparse使用有限状态机实现。
  • 推入解析器栈的值不仅仅看做是一个个的token，它们表示的是终结、非终结符组成的序列（栈顶的token序列），token就是状态机的状态。·
  • 每次读lookahead时，状态机的状态 和 lookahead一并去 “table”里面查出来一条转移指令。
  • 转移指令可能是shift：解析器堆栈入栈。
  • 转移指令可能是recude：解析器堆栈出栈状态（token/tolen序列），入栈一个替换的状态（token）。
mapreduce

0 人点赞