這是一個簡單但非常常見的 EBNF 格式的語法規則案例，Statementsis 一個無終結符和Statement無終結符：
Statements ::= (Statement ';')*
將此規則轉換為NFA后，再進行NFA轉換為DFA的子集構造，最終得到dfa：
State0 -> Statement -> State1 -> ';' ->State0
State0 -> ε -> State0
該State0是DFA的代表沒有終端符號開始的狀態Statements，也就是它的完成狀態。從State0輸入Statement和翻譯到State1輸入';' 在State1，轉換為State0。此外，State0可以用ε.
并且按照dragon book中的演算法將上述dfa轉換為常規語法后，我得到以下語法規則：
Statements -> ε
Statements -> Statement Extend_NT
Extend_NT -> ';' Statements
它添加了新的無終結符Extend_NT，但我想獲得以下不包含擴展符號的常規語法Extend_NT：
Statements -> ε
Statements -> Statement ';' Statements
所以問題是有沒有什么演算法可以得到不包含新的無終結符的上述結果Extend_NT？
還是只是工程問題？
uj5u.com熱心網友回復：
我不確定我是否理解你的問題。
如果你只是有一個單一生產用于非終端和生產只是有一個單一的重復操作，無論是在開始或結束時，你可以申請一個簡單的脫糖：（這里α和β是語法符號序列（但不是EBNF符號)，并且α可能為空。)
N ::= α (β)* ? N → α | N β
N ::= (β)* α ? N → α | β N
如果α為空，則可以使用上述任何一種。對于 LALR(1) 決議器生成器，通常選擇左遞回版本；如果您正在構建一個 LL 決議器，您當然需要右遞回版本。
如果右側有多個 EBNF 運算子，那么您將需要額外的非終結符，每個 EBNF 重復運算子一個，可能除了一個。
我不知道你是否會稱其為演算法。我個人認為是工程，但區別不是絕對的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/364382.html