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

1 lookahead token

學(xué)習(xí)yacc后一直有一個疑問，reduce到底什么時候發(fā)生？
遇到匹配的規(guī)則立即執(zhí)行reduce嗎？還是在等一等看看后面的token，可能匹配上其他的規(guī)則？

bison行為：

• bison解析器并不是遇到棧頂?shù)囊唤Mtoken匹配上規(guī)則后，立即執(zhí)行recude。因為這種簡單的策略不能滿足一些復(fù)雜語言的需要。
• bison解析器在發(fā)現(xiàn)一次匹配后，會繼續(xù)向前看一個lookahead，再決定做什么。

具體步驟：

當(dāng)讀到一個token時，并不立即shift進入堆棧，而是把他當(dāng)成lookahead token（不入棧）。

然后解析器就可以執(zhí)行棧上的匹配動作了，匹配上就可以reduce。lookahead token放在一邊。

當(dāng)沒有token能進行reduce后，再把lookahead token shift入棧。

上面的步驟2并不是匹配上的都能reduce，lookahead token會影響一些規(guī)則，使其延遲reduce。

1.1 lookahead token案例分析

• 這是一個有相互依賴關(guān)系的語法樹。term可以reduce為expr；expr加括號可以reduce為term。
• !是后綴運算符，表示階乘。
• 語法支持括號分組。

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

當(dāng)1+2進入語法樹時，如果不向前看一個token，會發(fā)生的問題：

1 + 2 )\ /1 + 2 reduce為：expr ')'\ /expr 和 右括號reduce為term

如果1+2后面跟的是!，上面的1+2已經(jīng)被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"終結(jié)符

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

假設(shè)當(dāng)前"if"、“then"都已經(jīng)在解析棧中，lookahead是"then”。

• 選擇1：當(dāng)前解析棧按規(guī)則1規(guī)約。
• 選擇2：lookahead繼續(xù)shift入棧，按規(guī)則2規(guī)約。

現(xiàn)在發(fā)生了shift/reduce沖突。Bison會通過選擇shift來解決這些沖突（除非運算符優(yōu)先級聲明）。

3.1 懸掛沖突

為了解其中的原因，下面與其他選擇進行對比：

正例：如果bison更偏向于shift “else”，下面語句1就等價與語句2，符合預(yù)期。

-- 語句1 if x then if y then win; else lose;-- 語句2：else和里面的If結(jié)合，符合預(yù)期 if x then do; if y then win; else lose; end;

反例：如果bison更偏向于reduce，下面語句1就等價與語句2，不符合預(yù)期。

能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結(jié)合，不符合預(yù)期。 if x then do; if y then win; end; else lose; -- 結(jié)果就是else給外面的if了，但預(yù)期是需要和里面的if結(jié)合。

這就是經(jīng)典的“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 93 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" stmtExample: "if" expr "then" "if" expr "then" stmt ? "else" stmtShift derivationif_stmt? 3: "if" expr "then" stmt? 2: if_stmt? 4: "if" expr "then" stmt ? "else" stmtReduce derivationif_stmt? 4: "if" expr "then" stmt "else" stmt? 2: if_stmt? 3: "if" expr "then" stmt ?

3 解析器狀態(tài)

• yyparse使用有限狀態(tài)機實現(xiàn)。
• 推入解析器棧的值不僅僅看做是一個個的token，它們表示的是終結(jié)、非終結(jié)符組成的序列（棧頂?shù)膖oken序列），token就是狀態(tài)機的狀態(tài)。·
• 每次讀lookahead時，狀態(tài)機的狀態(tài) 和 lookahead一并去 “table”里面查出來一條轉(zhuǎn)移指令。
• 轉(zhuǎn)移指令可能是shift：解析器堆棧入棧。
• 轉(zhuǎn)移指令可能是recude：解析器堆棧出棧狀態(tài)（token/tolen序列），入棧一個替換的狀態(tài)（token）。

總結(jié)

以上是生活随笔為你收集整理的bison解析中lookahead前瞻工作原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。