编译原理-实验⼆-FLEX词法分析器FLEX词法分析器⼀、Lex和Yacc介绍Lex 是⼀种⽣成扫描器的⼯具。
扫描器是⼀种识别⽂本中的词汇模式的程序。
⼀种匹配的常规表达式可能会包含相关的动作。
这⼀动作可能还包括返回⼀个标记。
当 Lex 接收到⽂件或⽂本形式的输⼊时，它试图将⽂本与常规表达式进⾏匹配。
它⼀次读⼊⼀个输⼊字符，直到找到⼀个匹配的模式。
如果能够找到⼀个匹配的模式，Lex 就执⾏相关的动作（可能包括返回⼀个标记）。
另⼀⽅⾯，如果没有可以匹配的常规表达式，将会停⽌进⼀步的处理，Lex 将显⽰⼀个错误消息。
Yacc代表 Yet Another Compiler Compiler 。
Yacc 的 GNU 版叫做 Bison。
它是⼀种⼯具，将任何⼀种编程语⾔的所有语法翻译成针对此种语⾔的 Yacc 语法解析器。
（下载下载flex和bison。
⽹址分别是/packages/flex.htm和/packages/bison.htm。
）⼆、配置环境（win7）①下载flex和bison并安装到D:\GnuWin32（尽量是根⽬录）②由于我们使⽤的flex和bison都是GNU的⼯具，所以为了⽅便，采⽤的C/C++编译器也采⽤GNU的编译器GCC，当然我们需要的也是Windows版本的GCC了。
所以提前准备好VC 6.0③检验是否可以进⾏lex⽂件编译1.新建⽂本⽂件，更改名称为lex.l，敲⼊下⾯代码%{int yywrap(void);%}%%%%int yywrap(void){return 1;}2.新建⽂本⽂件，更改名称为yacc.y,敲⼊下⾯代码%{void yyerror(const char *s);%}%%program:;%%void yyerror(const char *s){}int main(){yyparse();}我们暂且不讨论上⾯代码的意思。
打开控制台，进⼊到刚才所建⽴⽂件（lex.l,yacc.y）所在的⽂件夹。
编译原理词法分析与语法分析的核心算法编译原理是计算机科学与技术领域中的一门重要课程。
在编程中，我们常常需要将高级语言编写的程序翻译成机器语言，使计算机能够理解并执行我们编写的程序。
而编译原理中的词法分析和语法分析是编译器的两个核心算法。
一、词法分析词法分析是编译器的第一个阶段，它负责将输入的字符序列（源代码）划分为一个个的有意义的词素（Token），并生成相应的词法单元（Lexeme）。
词法分析的核心算法主要包括以下两个步骤：1. 正则表达式到有限自动机的转换：正则表达式是一种描述字符串匹配模式的表达式，它可以用来描述词法分析中各种词素的规则。
而有限自动机则是一种用来识别或匹配正则表达式所描述的模式的计算模型。
将正则表达式转换为有限自动机是词法分析的关键步骤之一。
2. 词法分析器的生成：在将正则表达式转换为有限自动机后，我们可以使用生成器工具（如Lex、Flex等）来生成词法分析器。
词法分析器可以按照预定的规则扫描源代码，并将识别出的词素转换成相应的词法单元，供后续的语法分析使用。
二、语法分析语法分析是编译器的第二个阶段，它负责分析和处理词法分析阶段生成的词法单元序列，并根据预定的语法规则确定语法正确的序列。
语法分析的核心算法主要包括以下两个步骤：1. 上下文无关文法的定义：上下文无关文法（Context-Free Grammar，简称CFG）是一种用于描述形式语言的文法。
它由一组产生式和终结符号组成，可以用于描述语法分析中的语法规则。
在语法分析中，我们需要根据具体编程语言的语法规则，编写相应的上下文无关文法。
2. 语法分析器的生成：通过使用生成器工具（如Yacc、Bison等），我们可以根据上下文无关文法生成语法分析器。
语法分析器可以根据预先定义的文法规则，对词法单元序列进行分析，并构建出语法树（Parse Tree）供后续的语义分析和代码生成使用。
综上所述，词法分析与语法分析是编译原理中的两个重要阶段，也是实现编译器的核心算法。
编译原理-词法分析02-正则表达式0.术语rr：正则表达式，表⽰字符串的格式。
L(r)r所匹配的串的集合。
symbol符号L(r)中的元素称为符号。
alphabet字母表表⽰符号的字符的集合。
⽤ ∑ (sigma)表⽰。
元字符metacharacter，元符号metasymbol它们⾮字母表中的字符，是⼀些特殊意义的字符，⽐如,*. 如果要匹配这类符号，则需要使⽤转义符号\。
escape character转义字符⼀般使⽤\表⽰，⽤于匹配元字符。
空串empty string不包含任何字符的串，但它仍然是⼀个匹配。
⽤ε（eplsilon）表⽰空集empty set表⽰正则表达式⽆任何匹配。
regular definition正则定义即正则表达式的名字。
1.正则表达式的定义正则表达式是以下中的⼀种：1. 基本正则表达式由单个字符a(其中a在正规字符的字母表 ∑ 中)，以及元字符ε或元字符Φ。
分别表⽰为：L(a) = {a};L(ε) = {ε};L(Φ) = {}.2. r|s格式的表达式：其中r和s均是正则表达式。
在这种情况下：L(r|s) = L(r)|L(s)。
3. rs格式的表达式：其中r是正则表达式。
在这种情况下：L(rs) = L(r)L(s)。
4. r格式的表达式：其中r是正则表达式。
在这种情况下：L(r) = L(r)*。
5. (r)格式的表达式：其中r是正则表达式。
在这种情况下：L((r)) = L(r)，因此，括号并不改变语⾔，它们只调整运算的优先级。
注意到这个定义中，|,*,(,),Φ,ε均为元字符。
2.扩展r+ 正闭包，⾄少匹配⼀个. 匹配任意⼀个字符区间匹配如[a-z],[0-9],[A-Za-z]~a或^a 排除匹配r? 可选匹配3.程序语⾔记号的正则表达式numbernat = [0-9]+ #⾃然数signedNat = (+|-)?nat #有符号数number = signedNat("."nat)?(E signedNat)? #数字，包含整数，⼩数，正负数，指数reserved & identifierreserverd = if | while | then | repeat | do ...letter = [a-z]digit = [0-9]identifier = letter(letter|digit)*comment{(~})*} #匹配{ this is a Pascal comment}whitespace解决匹配的⼆义性遵循最长⼦串原理principle of longest。
