bison解析中lookahead前瞻工作原理

mingjie

发布于 2023-01-13 12:16:05

1.4K0

发布于 2023-01-13 12:16:05

文章被收录于专栏：Postgresql源码分析Postgresql源码分析

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

1 lookahead token

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

bison行为：

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

具体步骤：

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

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

1.1 lookahead token案例分析

这是一个有相互依赖关系的语法树。term可以reduce为expr；expr加括号可以reduce为term。
!是后缀运算符，表示阶乘。
语法支持括号分组。

expr:
  term '+' expr
| term
;

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

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

         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"终结符

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，符合预期。

-- 语句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了，

-- 语句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。

文件

%%
stmt:
  expr
| if_stmt
;

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

expr:
  "identifier"
;

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

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）。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-01-11，如有侵权请联系 cloudcommunity@tencent.com 删除

mapreduce

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

mapreduce

登录后参与评论

0 条评论

热度