递归下降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？

回答

相关问题