LL語法與關聯性和自我指涉產品

Question

我想寫一個語法分析器，目前有一個LL語法（在Antlr中）下面的產品，我試圖解析一個或多個（數字或字符串）是分離的由一個「＃」即是正確的聯想。我該如何修改這些作品，以便它可以解析由「＃」分隔的一個或多個字符串，而不僅僅是一個？對於這個語法語言

A ::= B 
    | Number 
    | String 

B ::= C "->" A 

C ::= Number 
    | String 

例子：

ABC# 123 
123 # ABC 
ABC# DEF # 123 
ABC# DEF # (123 # 456) 
ABC# (DEF # 123) # 456 

我嘗試使用EBNF形式

A ::= B 
    | Number 
    | String 
    | "(" A ")" 

B ::= C ("#" A)? 

C ::= Number 
    | String 

但引起我的語法是不明確的。我將如何解決這個模糊問題？

Answer 1

的不確定性來自於事實，你可以得到你Number或String兩種方式 - 直接A - >Number，或A - >B - >C - >Number（以及類似的String）。最明顯的解決方法是擺脫了直接製作的：

A ::= B 
    | "(" A ")" 

B ::= C ("#" A)? 

C ::= Number 
    | String 

Answer 2

我認爲你在尋找什麼是相當簡單一點：

A ::= B ("#" B)* 
B ::= Number | String | "(" A ")" 

不會過分ANTLR親，我不確定如何將#標記爲右聯合，但該規則的意圖是生成B s的列表，因此您可能可以將它們與語義規則中的權限相關聯。

將括號內的表達規則放在層次結構的底部（可以這麼說）很重要;否則，你將無法解析(first # second) # third。