LEX与YACC：优先级与结合性详解

本文主要讨论了编译原理中的核心概念——优先级和结合性，以及如何在LEX（LExical Analyzer）和YACC（Yet Another Compiler Compiler）工具中应用它们来自动生成编译器。LEX和YACC是用于构建词法分析器和语法分析器的传统工具，它们通常与BISON（GNU Bison）和FLEX（Fast Lexical Analyzer Generator）一起使用，构成一个高效的编译器生成器套件。 1. 优先级和结合性的定义： - 优先级和结合性是解析表达式时确定操作顺序的关键因素。%left和%right是用于定义操作符的结合性指令，%left表示左结合，即操作符的优先级遵循从左到右的执行顺序；%right表示右结合，优先级从右向左。 - 指令出现的次序决定了优先级的高低，也就是说，前面定义的优先级较低，后面定义的优先级较高。如果同一运算符在不同上下文中有不同的结合性和优先级，可以通过虚拟单词来解决这个问题。 2. LEX（词法分析器）： - LEX是一个强大的工具，用于从输入流中识别出特定的“单词”或模式，如数字、标识符等。它通过模式来定义词法单元，并可以处理各种元字符和转义序列。 - 例如，模式 "[0-9][0-9]*" 可以匹配一串连续的数字。 3. 编译程序生成的挑战： - 手动编写编译程序，特别是对于复杂的语法规则，工作量巨大且难以维护。例如，ANSI C的词法规则众多，可能导致大量的状态转换。 4. 自动化编译程序的利用： - LEX通过提供一个源文件（.l），可以自动生成处理词法的C代码（lex.yy.c）。用户还需编写主程序（如main()）和辅助函数（如yywrap()），以控制程序流程。 5. LEX源文件结构： - 分为定义部分、规则部分和用户附加的C代码部分。定义部分包含模式和运算符的优先级定义，规则部分定义了输入流中的模式如何映射到内部状态，而用户代码部分用于扩展或定制词法分析功能。 6. LEX源文件格式示例： - 例如，"TEST.L"文件展示了如何统计文本文件的行数和字符数，通过使用特定的模式（如\n表示换行符）来触发计数。 7. 使用LEX的过程： - 用户编写LEX源文件，然后通过flex工具生成C代码。接着，编译生成的lex.yy.c并链接到C程序中，形成可执行文件lex.yy.exe，用于处理输入文件。 总结来说，优先级和结合性在LEX和YACC中起着关键作用，它们帮助编译器解析复杂语法，而LEX则负责处理文本输入中的词法结构。通过自动化工具的使用，编译器的开发过程得到了显著简化，提高了效率和维护性。