使用Lex工具进行tiny+语言的词法分析

2024-02-09 02:48
文章标签 语言 分析 进行 工具 使用 tiny 词法 lex

本文主要是介绍使用Lex工具进行tiny+语言的词法分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

词法分析程序实验报告

实验环境

  • 架构：Intel x86_64 (虚拟机)
  • 操作系统：Ubuntu 20.04
  • 汇编器：gas (GNU Assembler) in AT&T mode
  • 编译器：gcc

实验目的

通过扩充已有的样例语言TINY语言的词法分析程序，为扩展TINY语言TINY+构造词法分析程序，从而掌握词法分析程序的构造方法。

实验内容

了解样例语言TINY及TINY编译器的实现，了解扩展TINY语言TINY+，用C语言在已有的TINY词法分析器基础上扩展，构造TINY+的词法分析程序。

实验要求

将TINY+源程序翻译成对应的TOKEN序列，并能检查一定的词法错误。

代码地址

代码地址

项目介绍

源程序：lex.yy.c
可执行程序：a.out

文件夹结构
tiny+
|-- a.out
|-- lex.yy.c
|-- Makefile
|-- scanner
|-- scanner.l
|-- test|-- ilegal_input.tny|-- test1.tny|-- test.tny
|-- token
|-- token.h
运行方式

进入tiny+文件夹目录，在终端输入：

./a.out < test/test.tny          // TINY+样例词法分析序列打印到终端
./a.out < test/test.tny > token  // TINY+样例词法分析序列生成到token文件
./a.out < test/test1.tny         // TINY+合法输入测试
./a.out < ilegal_input.tny       // TINY+词法错误测试

TINY语言

词法定义
  • 关键字：WRITE READ IF THEN ELSE RETURN BEGIN END MAIN STRING INT REAL REPEAT UNTIL
  • 单字符分隔符：; , ( )
  • 单字符运算符：+ - * /
  • 多字符运算符：:= == != =
  • 标识符：标识符由一个字母后跟任意数量的字母或数字组成。以下是标识符的示例：x、x2、xx2、x2x、End、END2。注意End是标识符，而END是关键字。以下不是标识符：
    • IF, WRITE, READ, ....（关键字不计为标识符）
    • 2x（标识符不能以数字开头）
    • 注释中的字符串不是标识符。
  • Number 是一个数字序列，或者是一个数字序列，后跟一个点，然后是数字。
    Number -> Digits | Digits '.' Digits
Digits -> Digit | Digit Digits
Digit  -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
  • 注释：/** 和 **/ 之间的字符串。注释可以超过一行。
EBNF 语法

高级程序结构：

Program -> MethodDecl MethodDecl* 
Type -> INT | REAL |STRING 
MethodDecl -> Type [MAIN] Id '(' FormalParams ')' Block
FormalParams -> [FormalParam ( ',' FormalParam )* ]
FormalParam -> Type Id

声明：

Block -> BEGIN Statement+ ENDStatement -> Block| LocalVarDecl  | AssignStmt   | ReturnStmt| IfStmt| WriteStmt| ReadStmtLocalVarDecl -> Type Id ';' | Type AssignStmt  AssignStmt  -> Id := Expression ';'|  Id := QString ';'
ReturnStmt -> RETURN Expression ';'
IfStmt    -> IF '(' BoolExpression ')' Statement| IF '(' BoolExpression ')' Statement ELSE Statement
WriteStmt -> WRITE '(' Expression ',' QString ')' ';'
ReadStmt  -> READ '(' Id ',' QString ')' ';'
QString 是除双引号本身之外的任何字符序列，用双引号括起来。

表达式：

Expression -> MultiplicativeExpr  (( '+' | '-' ) MultiplicativeExpr)*
MultiplicativeExpr -> PrimaryExpr (( '*' | '/' ) PrimaryExpr)*
PrimaryExpr -> Num  // Integer or Real numbers| Id            | '(' Expression ')'| Id '(' ActualParams ')'
BoolExpression -> Expression '==' Expression |Expression '!=' Expression   
ActualParams -> [Expression ( ',' Expression)*]

样例：

/** this is a comment line in the sample program **/
INT f2(INT x, INT y ) 
BEGIN INT z;z := x*x - y*y;RETURN z; 
END 
INT MAIN f1() 
BEGININT x;READ(x, "A41.input");INT y;READ(y, "A42.input");INT z;z := f2(x,y) + f2(y,x);WRITE (z, "A4.output"); 
END

TINY+

TINY+是对TINY语言的一个扩充，比TINY多了程序的声明部分，while语句，字符串类型定义等等。

词法定义
  • 关键字：在TINY的关键字write read if then else return begin end main string int real repeat until的基础上，扩充了or and bool char while do这几个关键字，小写字母表示，自定义标识符不能和关键字重复。
  • 特殊符号：在TINY的特殊符号; , ( ) + - * / := == != =的基础上，扩充了> < <= >= '这几个特殊符号。
  • 其他种类的单词包括标识符ID，数字NUM以及字符串STRING，他们的正规表达式的定义如下：
    • 标识符是以字母开头，由字母和数字混合构成的符号串：
      ID=letter (letter | digit)*
    • TINY+中对数字的定义和TINY相同：
      NUM=digit digit*
    • 一个字符串类型的单词是用单引号括起来的字符申’…'，引号内可出现除了’以外的任何符号。一个字符串不能跨行定义：
      STRING=any character except''
    • 小写和大写字母是不同的：
      letter=a|...|z|A|...|Z
digit=0|...|9
  • 空白包括空格、回车以及Tab。所有的空白在词法分析时，被当作单词ID, NUM以及保留字的分隔符，在词法分析之后，他们不被当作单词保留。
  • 注释是用花括号括起来的符号串{…}，注释不能嵌套定义，但注释的定义可以跨行。
EBNF 语法

和TINY相比，扩展的部分有：

Statement -> Block| LocalVarDecl  | AssignStmt   | ReturnStmt| IfStmt| WriteStmt| ReadStmt| WhileStmt| DoWhileStmt| ForStmtWhileStmt -> WHILE '(' BoolExpression ')' Statement
DoWhileStmt -> DO Statement WHILE '(' BoolExpression ')'
ForStmt -> For AssignStmt UPTO Expression DO Statement| For AssignStmt DOWNTO Expression DO StatementMultiplicativeExpr -> PrimaryExpr (( '*' | '/' | '%' ) PrimaryExpr)*
BoolExpression -> Expression '==' Expression| Expression '!=' Expression | Expression '>' Expression| Expression '<' Expression
样例

在之前TINY语言的样例基础上，使用TINY+将样例改动为：

{ this is a comment line in the sample program }
int f2(int x, int y ) 
begin int z;z := x*x - y*y;return z; 
end 
int main f1() 
beginint x;read(x, 'A41.input');int y;read(y, 'A42.input');int z;z := f2(x,y) + f2(y,x);write (z, 'A4.output'); 
end

实现过程

根据课程网站中有关lex工具的资料，可以通过lex生成C语言版的TINY+的词法分析程序。

首先安装lex工具：

在Linux上终端输入下列命令：

sudo apt-get install flex

然后在终端中输入：

lex --version

如果显示lex的版本，那么安装成功。

然后创建flex模式文件：

创建一个tiny+目录，进入这个目录中，创建一个scanner.l文件，输入下列内容：

%{
#include "token.h"
int cur_line_num = 1;
void lex_error(char* msg, int line);
%}/* Definitions */
KEY                 ("write"|"read"|"if"|"then"|"else"|"return"|"begin"|"end"|"main"|"string"|"int"|"real"|"or"|"and"|"int"|"bool"|"char"|"while"|"do"|"repeat"|"until")
SYM                 (";"|","|"("|")"|"+"|"-"|"*"|"/"|":="|"=="|"!="|">"|"<"|"<="|">="|"="|"'")
ID                  ([a-zA-z][a-zA-Z0-9]*)
NUM                 ([0-9][0-9]*)
STR                 (\'[^\'\n]*\')
UNTERM_STR1         ((\'[^\'\n]*))
UNTERM_STR2         (\'\n)
COMMENT             (\{[^\{\}]*\})
UNTERM_COMMENT      (\{[^\{\}]*[\{]*)
ILLEGAL_SYMBOL      ([^[a-zA-Z0-9]|";"|","|"("|")"|"+"|"-"|"*"|"/"|":="|"=="|"!="|">"|"<"|"<="|">="|"="|"'"])%%[\n]                { cur_line_num++;                       }
[ \t\r\a]+          { /* ignore all spaces */               }{KEY}               { return T_KEY;             }
{SYM}               { return T_SYM;             }
{ID}                { return T_ID;              }
{NUM}               { return T_NUM;             }
{STR}               { return T_STR;             }
{COMMENT}           { /* skip for comment */    }  {ILLEGAL_SYMBOL}    { lex_error("An illegal symbol was found", cur_line_num);                           }
{UNTERM_STR1}       { lex_error("The string is missing a closing quote", cur_line_num);                 }
{UNTERM_STR2}       { lex_error("The string is missing a closing quote", cur_line_num); cur_line_num++; }
{UNTERM_COMMENT}    { lex_error("The comment is missing a closing bracket", cur_line_num);              }<<EOF>>             { return 0; }%%int main(int argc, char* argv[]) {int token;while (token = yylex()) {print_token(token);printf("%s", yytext);printf(")\n");}return 0;
}void lex_error(char* msg, int line) {printf("\nError at line %-3d: %s\n\n", line, msg);
}int yywrap(void) {return 1;
}

flex 模式文件中，%{ 和 %} 之间的为 声明（Declarations） ，都是 C 代码，这些代码会被原样的复制到 lex.yy.c 文件中，一般在这里声明一些全局变量和函数，这样在后面可以使用这些变量和函数：

%{
#include "token.h"
int cur_line_num = 1;
void lex_error(char* msg, int line);
%}

cur_line_num用来记录当前扫描到的行号。

%} 和 %% 之间的为 定义（Definitions），在这里可以定义正则表达式中的一些名字，可以在 规则（Rules） 段被使用，如本文件中定义了 NUM 为 ([0-9][0-9]*) ， 这样在后面可以用 {NUM} 代替这个正则表达式，这里根据TINY+语言的要求，定义了五个单词种类，并定义了出现词法错误时进行匹配的串：

/* Definitions */
KEY                 ("write"|"read"|"if"|"then"|"else"|"return"|"begin"|"end"|"main"|"string"|"int"|"real"|"or"|"and"|"int"|"bool"|"char"|"while"|"do"|"repeat"|"until")
SYM                 (";"|","|"("|")"|"+"|"-"|"*"|"/"|":="|"=="|"!="|">"|"<"|"<="|">="|"="|"'")
ID                  ([a-zA-z][a-zA-Z0-9]*)
NUM                 ([0-9][0-9]*)
STR                 (\'[^\'\n]*\')
UNTERM_STR1         ((\'[^\'\n]*))
UNTERM_STR2         (\'\n)
COMMENT             (\{[^\{\}]*\})
UNTERM_COMMENT      (\{[^\{\}]*[\{]*)
ILLEGAL_SYMBOL      ([^[a-zA-Z0-9]|";"|","|"("|")"|"+"|"-"|"*"|"/"|":="|"=="|"!="|">"|"<"|"<="|">="|"="|"'"])
  • KEY表示关键字；
  • SYM表示特殊符号；
  • ID表示标识符；
  • NUM表示数字常量
  • STR表示字符串常量
  • COMMENT表示注释
  • ILLEGAL_SYMBOL表示非法符号，词法分析器可能识别到一个TINY+程序的字母表中不允许的符号，比如识别到$，那么应报告一个词法错误，发现了一个非法符号；
  • UNTERM_STR1和UNTERM_STR2表示单引号不匹配，例如出现’ scanner，应报告错误“字符串缺少右引号”；
  • UNTERM_COMMENT表示注释的括号不匹配，例如出现{this is an example，应报告错误“注释缺少右括号”。

%% 和 %% 之间的内容被称为 规则（rules），本文件中每一行都是一条规则，每条规则由 匹配模式（pattern） 和 事件（action） 组成， 模式在前面，用正则表达式表示，事件在后面，即 C 代码。每当一个模式被匹配到时，后面的 C 代码被执行。

简单来说，flex 会将本段内容翻译成一个名为 yylex 的函数，该函数的作用就是扫描输入文件（默认情况下为标准输入），当扫描到一个完整的、最长的、可以和某条规则的正则表达式所匹配的字符串时，该函数会执行此规则后面的 C 代码。如果这些 C 代码中没有 return 语句，则执行完这些 C 代码后， yylex 函数会继续运行，开始下一轮的扫描和匹配。

当有多条规则的模式被匹配到时， yylex 会选择匹配长度最长的那条规则，如果有匹配长度相等的规则，则选择排在最前面的规则。

%%[\n]                { cur_line_num++;                       }
[ \t\r\a]+          { /* ignore all spaces */               }{KEY}               { return T_KEY;             }
{SYM}               { return T_SYM;             }
{ID}                { return T_ID;              }
{NUM}               { return T_NUM;             }
{STR}               { return T_STR;             }
{COMMENT}           { /* skip for comment */    }  {ILLEGAL_SYMBOL}    { lex_error("An illegal symbol was found", cur_line_num);                           }
{UNTERM_STR1}       { lex_error("The string is missing a closing quote", cur_line_num);                 }
{UNTERM_STR2}       { lex_error("The string is missing a closing quote", cur_line_num); cur_line_num++; }
{UNTERM_COMMENT}    { lex_error("The comment is missing a closing bracket", cur_line_num);              }<<EOF>>             { return 0; }%%
  • 匹配到了普通单词种类KEY、SYM、ID、NUM、STR会返回一个值，在token.h文件中进行相应的组合token和打印处理；
  • 匹配到了注释COMMENT直接跳过，不做任何处理；
  • 匹配到了非法符号ILLEGAL_SYMBOL直接跳过该行后面所有内容，并报告错误An illegal symbol was found和行号。
  • 匹配到了单引号不匹配UNTERM_STR1和UNTERM_STR2直接跳过该行后面所有内容，并报告错误The string is missing a closing quote和行号。
  • 匹配到了注释的括号不匹配UNTERM_COMMENT直接跳过后面所有内容，并报告错误The comment is missing a closing bracket和行号。

最后的 main 函数是程序的入口， flex 会将这些代码原样的复制到 lex.yy.c 文件的最后面：

int main(int argc, char* argv[]) {int token;while (token = yylex()) {print_token(token);if (token == (int)TokenType.T_STR) {int i = 1;while (yytext[i] != '\'') {printf("%c", yytext[i]);i++;}}else {printf("%s", yytext);}printf(")\n");}return 0;
}void lex_error(char* msg, int line) {printf("\nError at line %-3d: %s\n\n", line, msg);
}int yywrap(void) {return 1;
}

接着创建token.h文件：

在同一个文件目录下，创建token.h文件，并输入内容：

#ifndef TOKEN_H
#define TOKEN_Htypedef enum {T_KEY = 256, T_SYM, T_ID, T_NUM, T_STR
} TokenType;static void print_token(int token) {static char* token_strs[] = {"KEY", "SYM", "ID", "NUM", "STR"};if (token < 256) {printf("%-20c", token);} else z{printf("(%s, ", token_strs[token-256]);}
}#endif

最后创建Makefile文件：

在同一个文件目录下，创建token.h文件，并输入内容：

out: scannerscanner: lex.yy.c token.hgcc -o $@ $<lex.yy.c: scanner.lflex $<

生成源程序和可运行程序：

进入文件目录下，在终端输入make，生成源程序lex.yy.c和可运行程序scanner。

在终端再输入：

gcc lex.yy.c

也可生成可运行程序a.out

测试报告

样例TINY+测试

在tiny+文件夹目录，创建一个test文件夹，在这个文件夹中，创建一个test.tny文件，并把TINY+样例放进这个文件里面：

{ this is a comment line in the sample program }
int f2(int x, int y ) 
begin int z;z := x*x - y*y;return z; 
end 
int main f1() 
beginint x;read(x, 'A41.input');int y;read(y, 'A42.input');int z;z := f2(x,y) + f2(y,x);write (z, 'A4.output'); 
end

回到tiny+文件夹目录，在终端输入：

./scanner < test/test.tny

或

./a.out < test/test.tny

可以看到：

请添加图片描述

请添加图片描述

词法分析成功。

生成token序列，在终端输入：

./a.out < test/test.tny > token

可以看到：

请添加图片描述

词法分析的token序列已经被生成到了token文件中。

合法输入测试

在test文件夹，创建一个test1.tny文件，输入下列内容：

or and int bool char
while do if then else
end repeat until read write
, ; := + -
* / ( ) <
= > <= >= a2c
123 'EFG'
{ this is an example }
{ this 
is 
an 
example
}

对所有的关键字KEY、特殊符号SYM、符合格式要求的标识符ID、符号格式要求的数组常量NUM、符号格式要求的字符串常量STR、单行和多行注释COMMENT进行测试，回到tiny+文件夹目录，在终端输入：

./a.out < test/test1.tny

可以看到：

请添加图片描述

所有的合法输入KEY、SYM、ID、NUM、STR都被识别出来并组成token序列，单行和多行注释也被去掉。

词法错误测试

在test文件夹，创建一个ilegal_input.tny文件，输入下列内容：

$
#
' scanner
scanner '
{ this is a comment line in the sample program

对非法符号错误、单引号不匹配错误、注释的括号不匹配错误进行测试，回到tiny+文件夹目录，在终端输入：

./a.out < ilegal_input.tny

可以看到：

请添加图片描述

第1行和第2行的非法符号$和#被识别出来并报告错误An illegal symbol was found发现非法符号，第3行和第4行后面的单引号不匹配被识别出来并报告错误The string is missing a closing quote没有右引号，第5行的注释的括号不匹配被识别出来并报告错误The comment is missing a closing bracket没有右括号。

这篇关于使用Lex工具进行tiny+语言的词法分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/692918。

相关文章

java图像识别工具类(ImageRecognitionUtils)使用实例详解

java图像识别工具类(ImageRecognitionUtils)使用实例详解

《java图像识别工具类(ImageRecognitionUtils)使用实例详解》：本文主要介绍如何在Java中使用OpenCV进行图像识别,包括图像加载、预处理、分类、人脸检测和特征提取等步骤... 目录前言1. 图像识别的背景与作用2. 设计目标3. 项目依赖4. 设计与实现 ImageRecogni
阅读更多...
python管理工具之conda安装部署及使用详解

python管理工具之conda安装部署及使用详解

《python管理工具之conda安装部署及使用详解》这篇文章详细介绍了如何安装和使用conda来管理Python环境,它涵盖了从安装部署、镜像源配置到具体的conda使用方法,包括创建、激活、安装包... 目录pytpshheraerUhon管理工具：conda部署+使用一、安装部署1、 下载2、 安装3
阅读更多...
Mysql虚拟列的使用场景

Mysql虚拟列的使用场景

《Mysql虚拟列的使用场景》MySQL虚拟列是一种在查询时动态生成的特殊列,它不占用存储空间,可以提高查询效率和数据处理便利性,本文给大家介绍Mysql虚拟列的相关知识,感兴趣的朋友一起看看吧... 目录1. 介绍mysql虚拟列1.1 定义和作用1.2 虚拟列与普通列的区别2. MySQL虚拟列的类型2
阅读更多...
使用MongoDB进行数据存储的操作流程

使用MongoDB进行数据存储的操作流程

《使用MongoDB进行数据存储的操作流程》在现代应用开发中,数据存储是一个至关重要的部分,随着数据量的增大和复杂性的增加,传统的关系型数据库有时难以应对高并发和大数据量的处理需求,MongoDB作为... 目录什么是MongoDB？MongoDB的优势使用MongoDB进行数据存储1. 安装MongoDB
阅读更多...
关于@MapperScan和@ComponentScan的使用问题

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@
阅读更多...
mysql数据库分区的使用

mysql数据库分区的使用

《mysql数据库分区的使用》MySQL分区技术通过将大表分割成多个较小片段,提高查询性能、管理效率和数据存储效率,本文就来介绍一下mysql数据库分区的使用,感兴趣的可以了解一下... 目录【一】分区的基本概念【1】物理存储与逻辑分割【2】查询性能提升【3】数据管理与维护【4】扩展性与并行处理【二】分区的
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
Linux使用fdisk进行磁盘的相关操作

Linux使用fdisk进行磁盘的相关操作

《Linux使用fdisk进行磁盘的相关操作》fdisk命令是Linux中用于管理磁盘分区的强大文本实用程序,这篇文章主要为大家详细介绍了如何使用fdisk进行磁盘的相关操作,需要的可以了解下... 目录简介基本语法示例用法列出所有分区查看指定磁盘的区分管理指定的磁盘进入交互式模式创建一个新的分区删除一个存
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
SpringBoot使用Apache Tika检测敏感信息

SpringBoot使用Apache Tika检测敏感信息

《SpringBoot使用ApacheTika检测敏感信息》ApacheTika是一个功能强大的内容分析工具,它能够从多种文件格式中提取文本、元数据以及其他结构化信息,下面我们来看看如何使用Ap... 目录Tika 主要特性1. 多格式支持2. 自动文件类型检测3. 文本和元数据提取4. 支持 OCR（光学
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2