我曾经使用Lex执行某些代码,每当发现一些正则表达式时会执行, Yacc能做比这更多的事情吗?如果是,那么是什么?
是的,YACC是一个语法分析器,而Lex则是一个词法分析器。它们通常一起使用:你用Lex处理字符串输入,然后用YACC处理由Lex提供的标记化输入。
现在,正则表达式只能表示正则语言。正则语言的限制之一是缺乏“记忆”。您无法根据之前的内容定义更深层次的接受规则。
这在括号的情况下最明显。正则语言不能将嵌套的括号与正确的级别匹配。或者任何其他类似结构。大多数计算机语言的语法可以并且确实可以做到这一点,因此它们不能使用Lexer或正则表达式进行解析。这就是YACC发挥作用的地方。
也可以反过来问同样的问题。如果YACC可以做更多的事情,为什么不用它进行词法分析?嗯,事实上,您可以非常高效地验证正则表达式的有效性,但对于普通语法来说,并非如此--不能以相同的级别进行验证。尽管如此,如果语言的词法规则足够简单,YACC仍然可以进行基本的词法分析。
lex用于将输入进行分词,也就是将输入分离成语法规则定义的最基础的单元。例如,您可以使用lex来确定关键字、标识符、字符串、注释、空格等。
yacc用于解析您的语法。语法描述了您的语言,通常在EBNF或其他上下文无关文法中定义。一旦您向yacc描述了您的语法,您就可以使用它来在识别出语言元素时运行工具的操作。这可能包括构建表达式求解的语法树、定义作用域对象、记录变量定义等。
它们是互补产品。
通常情况下,lex和yacc是一起使用的。以下是通常使用两者构建应用程序的方法:
输入流(字符)-> Lex(标记)- > Yacc(抽象语法树)- > 您的应用
更一般地说,Lex将会从开头读取源文件,并尝试匹配许多正则表达式(Lex有自己的特殊语法,与Perl或sed不同),然后对于每个识别出来的标记将调用另一个程序。标记可以是普通的枚举值,如关键字或运算符,也可以附加一些元数据,如文字值。
通常使用Lex(虽然不是必须的)来调用Yacc。Yacc使用LALR解析器算法,大致上的工作原理是将每个标记推到堆栈上。如果堆栈具有它能够识别的标记序列,它将弹出所有标记,执行操作,然后将另一个标记推回堆栈。
Yacc工作的正确术语实际上是终端和非终端。终端是从调用程序(通常是Lex)获取的标记,而非终端是匹配其堆栈上的序列的结果。
通常,每个Yacc规则采取的操作是计算与规则对应的计算结果,或生成中间表示,例如语法树,供另一个应用程序层处理。
像Lex一样,Yacc也可以单独使用。例如,您可以通过向源文本传递单个字符来使用Yacc,并使用Yacc规则识别每种标记。但是,Yacc不是为以这种方式使用而设计的,因此生成的词法分析器将比在Lex中等效的词法分析器更复杂。更典型的用法是出于性能或需要更智能的词法分析器的原因制作手工编码的词法分析器。第二种情况的常见示例是在类似C的语言中使用,这些语言必须了解标识符的先前使用情况,以确定它们是否用于描述类型或变量。
Lex是用于构建词法分析器的工具,可以执行一些相当愚蠢的词法操作(如查找关键字)。Yacc是一个解析器生成器,可以为真正的计算机语言创建解析器。它的分析通常基于lex的输出(即令牌流),并从此可以创建编程语言的解析树——这比lex做的更多。
传统上,编译器构建者区分词法和语法分析——这是编译器中的两个重要步骤(后续步骤包括代码创建、优化等)。