遞歸下降vs Lex/Parse？

我想我大致理解遞歸下降解析器（例如Scala的解析器組合器）的工作原理：用一個解析器解析輸入字符串，解析器爲整個輸入的每個「部分」調用其他較小的解析器，等等直到你到達低級別的分析器，它們直接從輸入字符串的片段生成AST遞歸下降vs Lex/Parse？

我還認爲我理解Lexing/Parsing的工作原理：首先運行一個詞法分析器，將整個輸入分解爲令牌，然後運行解析器來獲取令牌列表並生成AST。

但是，我不明白的是，Lex/Parse策略如何處理如何標記化某些事情取決於先前標記化的標記的情況。例如，如果我採取XML的塊：

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>"

甲遞歸下降解析器可藉此與打破它（每個後續縮進表示父串的分解）

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>" 
    -> "<tag attr='moo' omg='wtf'>" 
     -> "<tag" 
     -> "attr='moo'" 
      -> "attr" 
      -> "=" 
      -> "moo" 
     -> "omg='wtf'" 
      -> "omg" 
      -> "=" 
      -> "wtf" 
     -> ">" 
    -> "attr='moo' omg='wtf'" 
    -> "</tag>"

而然後單獨解析的小解析器<tag,attr="moo"等將構建XML標籤的表示並向其添加屬性。

但是，單步Lex/Parse是如何工作的？ Lexer如何知道<tag之後和>之前的字符串必須被標記爲單獨的屬性，而>和</tag>之間的字符串不必是？是不是需要解析器告訴它第一個字符串在標籤體內，第二個情況是在標籤體外？

編輯：改變了例子來更清楚

來源

2012-02-27 Li Haoyi

詞法分析器會產生類似於'LEFTANGLE IDENT = tag IDENT = attr EQ STRING = moo IDENT = omg'等的內容 – 2012-02-27 16:01:57

@ SK-logic：編輯該問題以闡明。我的疑惑是，如果標籤主體有attr ='moo''_sideside，那麼詞法分析器怎麼知道不會將它分解爲'IDENT = tag'，並將它標記爲一個大文本節點？ – 2012-02-27 16:27:13

好吧，我看到了 - 它不會用一個詞法分析器將這些東西標記爲一個單一的大字符串，你必須解構一個字符串回來（當然，要放掉所有的空格）。 – 2012-02-27 16:42:46

通常詞法分析器將有一個「模式」或「狀態」的設置，根據輸入而變化。例如，在看到<字符時，模式將變爲「標記」模式，詞法分析器將適當地標記，直到看到>。然後它將進入「內容」模式，詞法分析器將返回所有的attr='moo' omg='wtf'作爲單個字符串。編程語言詞法分析器，例如，處理字符串文字是這樣的：

string s1 = "y = x+5";

的y = x+5絕不會爲一個數學表達式來處理，然後轉身回字符串。它被識別爲字符串文字，因爲"會更改詞法分析器模式。

對於像XML和HTML這樣的語言，構建定製解析器可能比使用yacc，bison或ANTLR之類的解析器生成器之一更容易。它們的結構與編程語言不同，它更適合自動工具。

如果您的解析器需要將令牌列表重新轉換爲來自它的字符串，那麼這是設計中出現錯誤的標誌。你需要以不同的方式解析它。

來源

2012-02-27 16:59:06

說這些需要「上下文敏感的標記化」的語言需要複製詞法分析器中的一些分析器邏輯（關於詞法分析器的狀態機與Parser的狀態機部分匹配）是否正確？如果大量使用詞法分析器狀態，那麼這種方法會使詞法分析器/解析器分離出來嗎？而且這種遞歸下降比一步的lexing/parsing更普遍（即使不那麼好分離）？ – 2012-02-27 18:29:47

通常詞法分析器狀態將由詞法分析器本身來管理。上面的例子可以這樣完成。我確信有一些例子，解析器會與詞法分析器進行通信以改變其狀態。但我同意你的發言。如果你必須做很多工作，那麼這種語言並不適合這些工具，遞歸下降甚至特別的解析器都會更好。我認爲FORTRAN屬於這個類別。它早於自動化工具，也是大部分正式的解析理論，解析它的唯一方法是使用完全自定義的解析器。 – 2012-02-27 18:42:16

感謝您的回答！這是一直在困擾我一段時間，尤其是因爲大多數時候當我問「解析」我只聽到「正則表達式」和「lex/yacc」或「tokenizer/parser」，我一直認爲遞歸下降（解析器組合器）對於一些非常簡單的情況感覺更自然。很高興知道我不瘋狂=）。 – 2012-02-27 19:11:34

如何詞法分析器知道後，必須字符串被標記化到單獨的屬性，而之間>和字符串不需要呢？

它沒有。

是不是需要解析器告訴它第一個字符串在標籤體內內，而第二種情況是在標籤體外？

是的。

通常，詞法分析器將輸入流轉換爲標記的序列。令牌沒有上下文 - 也就是說，令牌具有相同的含義，無論它出現在輸入流中的什麼地方。一旦lexing過程完成，每個令牌就被視爲一個單元。

對於XML，生成的詞法分析器通常會識別整數，標識符，字符串文字等以及控制字符，如'<'和'>'，但不是整個標記。理解什麼是開放標籤，關閉標籤，屬性，元素等的工作留給瞭解析器。

來源

2012-02-27 17:41:26

遞歸下降vs Lex/Parse？

回答

相關問題