TINY语言的词法分析

实验目的

(评价依据，描述是否准确到位)

构造tiny语言的词法分析器（扫描器），要求利用第三方的lex工具进行构造。

构造出的扫描器，能够读入教材样例中给出的tiny语言的示例代码，分解成token输出。

 

 

实验设计

（评价依据实验方案设计是否合理）

词法分析

1、关键字: if, then, else, end, repeat, until, read, write. 所有的关键字都是保留字，且全部小写。

2、专用符号： +  - * / = < ( ) ; :=

这里只用了<，　没有使用>，:=为赋值符号

3、其它标记是ID和NUM, 通过下列正则表达式定义：

ID = letter+ NUM = digit+ letter = [a-zA-Z] digit = [0-9]

大写和小写是有区别的

4、空格是由空白、制表符和新行组成。它通常被忽略，除了它必须分开ID、NUM关键字

5、注释用{...}围起来，且不能嵌套。

DFA

TINY扫描程序的DFA如下图所示：

内容和步骤

1、代码：

/************************ * tiny.l * @author stzg * 2015-9-21 23:08 ************************/ %{ #include "stdio.h" #include "stdlib.h" %} INT_DEX [1-9][0-9]*|[0] INT_HEX [0][Xx]([1-9][0-9]*|[0]) INT_OCT [0][0-7] FLOAT [0-9]*[.][0-9]+([eE][+-]?[0-9]*|[0])?f? SEMI [;] COMMA [,] ASSIGNOP [=] RELOP [>]|[<]|[>][=]|[<][=]|[=][=]|[!][=](^[=]) PLUS [+] MINUS [-] STAR [*] DIV [/] AND [&][&] OR [|][|] DOT [.] NOT [!] TYPE int|float LP \( RP \) LB \[ RB \] LC \{ RC \} STRUCT struct RETURN return IF if ELSE else WHILE while SPACE [ \n\t] ID [a-zA-Z_][a-zA-Z_0-9]* /*end of definition*/ %% {SEMI} { printf("get semmi : %s\n", yytext); } {COMMA} { printf("get comma : %s\n", yytext); } {ASSIGNOP} { printf("get assignop : %s\n", yytext); } {INT_DEX} | {INT_HEX} | {INT_OCT} { printf("get an integer: %s\n", yytext); } {FLOAT} { printf("get a float: %s\n", yytext); } {PLUS} | {MINUS} | {DIV} | {STAR} { printf("get an operator: %s\n", yytext); } {RELOP} { printf("get a relop: %s\n", yytext); } {AND} | {OR} | {NOT} { printf("get a logic operator: %s\n", yytext); } {DOT} { printf("get a dot: %s\n", yytext); } {STRUCT} | {RETURN} | {IF} | {ELSE} | {WHILE} { printf("get keyword: %s\n", yytext); } {TYPE} { printf("get type: %s\n", yytext); } {LP} | {RP} | {LB} | {RB} { printf("get brackets : %s\n", yytext); } {SPACE} { /*ABANDON THESE CHARACTORS*/ } {ID} { printf("get an ID: %s\n", yytext); } {LC} { char c; do { c = input(); if (c == EOF) break; //if (c == '\n') lineno++; } while (c != '}'); } %% int yywrap() { return 1; } int main(int argc, char** argv) { if (argc > 1) { if (!(yyin = fopen(argv[1], "r"))) { perror(argv[1]); return 1; } } while (yylex()); return 0; }

2、结果：

输入：

{ Sample program in TINY language - computes factorial } read x; { input an integer } if 0 < x then { don't compute if x <= 0 } fact := 1; repeat fact := fact * x; x := x - 1 until x = 0; write fact { output factorial of x } end

输出：

实验结论:

1、理论基础（评价依据 理论知识非常清楚）

我们采用flex进行词法分析。flex是一个用来生成扫描器（scanners）的工具，其中扫描器就是可以识别文本中词法模式的程序。具体流程为：flex读取给定的输入文件，或标准输入（当没有给定文件名时）读取信息来生成一个扫描器。信息以正则表达式和C代码组成，这种形式称为规则（rule）。flex生成C源代码文件lex.yy.c，其中定义了一个函数yylex()。这个文件通过编译，并用-lfl 链接生成可执行文件。当可执行文件被执行时，它分析输入中可能存在的符合正则表达的内容。当找到任何一个与正则表达式相匹配内容时，相应的C 代码将被执行。

flex输入文件由三段组成：定义（definitions），规则（rules），用户代码（user code）

2、分析和总结（评价依据：是否能够对实验结果作出完整和准确的描述，是否能够捕捉到实验中的各种现象，是否有强的信息综合能力，是否能得出正确的结论。）

实验过程中需要配置flex和bison的环境变量，在对原输入串进行分析的预处理在嵌套判断上出现了问题，调试了几次后才发现是计数值应该减少2。通过这次实验对词法分析器的运行机制有了更深的了解，状态转换图让我了解了一些编程语言的词法分析器是怎么书写的。

3、对工具的评价（优缺点及其局限性的总结）

flex的设计目标就是生成一个高性能的扫描器。它已经对处理大量rule 做了优化。除了用-C 选项进行表格压缩之外，还有一些option/action 会影响到扫描器的速度。

比如JavaScript，就不适合使用flex作为词法分析器，JavaScript 正则表达式字面量和除法操作符的二义性, 很难用 lex 解决, 一般只用 lex 做很少的事情, 然后把真正含义的辨清延迟到 parse 阶段.

真正复杂的问题是bison搞不定的，譬如说C++需要语义分析和语法分析同时做，让语义分析的结果来指导语法分析到底要选择哪条grammar rule来resolve conflict

flex ++是一个类似于C ++的词法扫描程序，它作为flex包的一部分包含在内。 生成的代码不依赖于任何运行时或外部库，除了内存分配器（malloc或用户提供的替代），除非输入也依赖于它。 这在传统操作系统或C运行时，设施可能不可用的嵌入式和类似情况下非常有用。

Flex只能为C和C ++生成代码。要使用flex从其他语言生成的扫描程序代码，可以使用SWIG等语言绑定工具。

 

参考文章

Windows环境下lex入门

LEX/FLEX词法分析器

自己动手写编译器之TINY编译器词法分析

Yacc 与 Lex-词法分析器工具

编译原理实验一 TINY语言的词法分析