使用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。

相关文章

C语言中联合体union的使用

C语言中联合体union的使用

本文编辑整理自： http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=179471 一、前言 “联合体”(union）与“结构体”(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间, 一个结构变量的总长度是各成员长度之和。而在“联合”中,各成员共享一段内存空间, 一个联合变量
阅读更多...
揭秘未来艺术：AI绘画工具全面介绍

揭秘未来艺术：AI绘画工具全面介绍

📑前言 随着科技的飞速发展，人工智能（AI）已经逐渐渗透到我们生活的方方面面。在艺术创作领域，AI技术同样展现出了其独特的魅力。今天，我们就来一起探索这个神秘而引人入胜的领域，深入了解AI绘画工具的奥秘及其为艺术创作带来的革命性变革。 一、AI绘画工具的崛起 1.1 颠覆传统绘画模式 在过去，绘画是艺术家们通过手中的画笔，蘸取颜料，在画布上自由挥洒的创造性过程。然而，随着AI绘画工
阅读更多...
墨刀原型工具-小白入门篇

墨刀原型工具-小白入门篇

墨刀原型工具-小白入门篇 简介 随着互联网的发展和用户体验的重要性越来越受到重视，原型设计逐渐成为了产品设计中的重要环节。墨刀作为一款原型设计工具，以其简洁、易用的特点，受到了很多设计师的喜爱。本文将介绍墨刀原型工具的基本使用方法，以帮助小白快速上手。 第一章：认识墨刀原型工具 1.1 什么是墨刀原型工具 墨刀是一款基于Web的原型设计工具，可以帮助设计师快速创建交互原型，并且可以与团队
阅读更多...
Tolua使用笔记（上）

Tolua使用笔记（上）

目录   1.准备工作 2.运行例子 01.HelloWorld：在C#中，创建和销毁Lua虚拟机 和 简单调用。 02.ScriptsFromFile：在C#中，对一个lua文件的执行调用 03.CallLuaFunction：在C#中，对lua函数的操作 04.AccessingLuaVariables：在C#中，对lua变量的操作 05.LuaCoroutine：在Lua中，
阅读更多...
大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
Vim使用基础篇

Vim使用基础篇

本文内容大部分来自 vimtutor，自带的教程的总结。在终端输入vimtutor 即可进入教程。 先总结一下，然后再分别介绍正常模式，插入模式，和可视模式三种模式下的命令。 目录 看完以后的汇总 1.正常模式（Normal模式） 1.移动光标 2.删除 3.【:】输入符 4.撤销 5.替换 6.重复命令【. ; ,】 7.复制粘贴 8.缩进 2.插入模式 INSERT
阅读更多...
Lipowerline5.0 雷达电力应用软件下载使用

Lipowerline5.0 雷达电力应用软件下载使用

1.配网数据处理分析 针对配网线路点云数据，优化了分类算法，支持杆塔、导线、交跨线、建筑物、地面点和其他线路的自动分类；一键生成危险点报告和交跨报告；还能生成点云数据采集航线和自主巡检航线。 获取软件安装包联系邮箱:2895356150@qq.com，资源源于网络，本介绍用于学习使用，如有侵权请您联系删除！ 2.新增快速版，简洁易上手 支持快速版和专业版切换使用，快速版界面简洁，保留主
阅读更多...
如何免费的去使用connectedpapers？

如何免费的去使用connectedpapers？

免费使用connectedpapers 1. 打开谷歌浏览器2. 按住ctrl+shift+N,进入无痕模式3. 不需要登录（也就是访客模式）4. 两次用完，关闭无痕模式（继续重复步骤 2 - 4） 1. 打开谷歌浏览器 2. 按住ctrl+shift+N,进入无痕模式 输入网址：https://www.connectedpapers.com/ 3. 不需要登录（也就是
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
[职场] 公务员的利弊分析 #知识分享#经验分享#其他

[职场] 公务员的利弊分析 #知识分享#经验分享#其他

公务员的利弊分析     公务员作为一种稳定的职业选择，一直备受人们的关注。然而，就像任何其他职业一样，公务员职位也有其利与弊。本文将对公务员的利弊进行分析，帮助读者更好地了解这一职业的特点。 利： 1. 稳定的职业：公务员职位通常具有较高的稳定性，一旦进入公务员队伍，往往可以享受到稳定的工作环境和薪资待遇。这对于那些追求稳定的人来说，是一个很大的优势。 2. 薪资福利优厚：公务员的薪资和
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2