解析上下文敏感的語言

Question

我被特倫斯·帕爾，他說讀權威ANTLR參考：

語義謂詞是識別上下文敏感 語言結構的有力 手段使 運行信息來推動 承認

但書中的例子很簡單。我需要知道的是：可以ANTLR解析context-sensitive規則，如：

XAY - > XBY

如果ANTLR不能解析這些規則，是有另一種工具，與上下文相關的語法交易？

Answer 1

ANTLR只解析LL（*）的文法。它無法使用語法解析完整的上下文敏感語言，例如您提供的示例。我認爲Parr的意思是ANTLR可以解析一些需要一些（左）上下文約束的語言。

特別是，人們可以使用「減排行動」的語義謂詞（我們這樣做對我們DMS Software Reengineering Toolkit但這個想法是對ANTLR類似，我認爲使用GLR分析器 ）檢查到目前爲止解析器收集的任何數據，或者作爲其他語義行爲的臨時副作用，或者是部分構建的分析樹。

對於我們的基於DMS的DMS-based Fortran front end，有一個上下文相關的檢查來確保DO循環正確排列。試想一下：

DO 20, I= ... 
    DO 10, J = ... 
     ... 
20 CONTINUE 
10 CONTINUE 

但從解析器的角度來看，詞法流是這樣的：

DO <number> , <variable> = ... 
    DO <number> , <variable> = ... 
     ... 
<number> CONTINUE 
<number> CONTINUE 

如何解析器後來才知道里面做陳述與哪個CONTINUE語句？ （說每個DO與其最接近的CONTINUE匹配將不起作用，因爲FORTRAN可以通過 與多個DO頭共享一個CONTINUE語句）。

我們使用語義謂詞「CheckMatchingNumbers」關於以下規則的減少：

block = 'DO' <number> rest_of_do_head newline 
     block_of_statements 
     <number> 'CONTINUE' newline ; CheckMatchingNumbers 

檢查該做關鍵字後的數字，而數字之後的CONTINUE關鍵字匹配。如果語義謂詞表示它們匹配，則此規則的減少會成功，並且我們已將DO頭與正確的CONTINUE對齊。如果謂詞失敗，則不會提出約簡（並且將此規則從候選解析本地上下文中刪除）;其他一些規則必須解析文本。

處理FORTRAN嵌套與共享繼續的實際規則和語義謂詞比這更復雜，但我認爲這說明了一點。

你想要的是完整的上下文相關的解析引擎。我知道人們已經建立了它們，但我不知道有什麼完整的實現，也不希望它們速度很快。

我確實按照Quinn Taylor Jackson's MetaS grammar system一段時間;這聽起來像是一個實際嘗試接近。