0. 说明

这是一个编译原理课的大作业，我自己实现了一个正则语法分析器（从输入字符流到Token序列）和LALR(1)语法分析器（Token序列到规约产生式序列）。以下是说明文档。

项目是放在一个repo的子文件夹里的，目录是：https://github.com/ddadaal/Homework/tree/master/Compiler/CompilerLab

编译原理实验报告

1. 目标

实现一个能解析正则表达式和一些扩展语法的通用词法分析器，和使用LALR(1)进行语法分析的语法分析器，并定义一个能够以上提到的分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式，并能够做到通过在系统指定的可用Token集合上，从用户给定的词法定义文件和语法定义文件，实现从输入文件到产生式规约序列的全过程。

2. 内容描述

本实验提供了以下内容：

一个Intellij IDEA格式的Java项目，包含了目标中提到的词法分析器、语法分析器以及对应分析器的一些测例。
能被分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式描述
以龙书上例题4.31为依据的输入文件、输出文件、myl词法定义文件和myy语法定义文件，并提供了对应的测例
一个C语言子集的输入文件、输出文件、myl词法定义文件和myy语法定义文件。同时还提供了与其中myl和myy等价的flex/bison定义文件以及对应的一些工具程序。提供的词法定义和语法定义已经经过flex和bison测试可以完整无错误的解析提供的输入文件。

2.1 词法定义文件格式myl

一个myl包含数个以下格式的词法定义，每个定义之间可接受任意个数的空行。

第一行：正则表达式的字符串
第二行：对应的TokenType的字符串

其中，正则表达式支持以下元素：

字符字面量
闭包（*）
并集（|）
覆写优先级的括号（(, )）
escaped字符(\n, \t, \b，", \ (空格，表示一个空格), \+, \*, \(, \), \r)

扩展支持：

方括号([])

方括号内部出现的元素之间会通过并集|连接，可与字符类配套使用。

例如：[ac\n]等价于(a|c|\n)

字符类（-），只能出现在方括号中

在ASCII表中，-前面的符号和后面的符号之间的所有符号会通过并集|连接。

例如：[a-d]等价于(a|b|c|d)

例如：[\n\ba-d_]等价于(\n|\b|(a|b|c|d)|_)

示例：

\+
PLUS （定义一个正则表达式为\+，对应到PLUS类型的Token的匹配规则，）

\*
STAR（定义一个正则表达式为\*，对应到STAR类型的token的匹配规则）

\(
LEFT_PARENTHESIS

\)
RIGHT_PARENTHESIS

[a-zA-Z]([0-9a-zA-Z_])*
IDENTIFIER （定义一个正则表达式为[a-zA-Z]([0-9a-zA-Z_])*（即以字母开头，后面跟任意个数的数字、字母或下划线），对应到IDENTIFIER类型的token转换规则）

[\ \n\r]
IGNORED （定义空格、空行或\r字符都被匹配到IGNORED类型的token的转换规则）

2.2 语法分析文件格式myy

一个myy文件以一个字符串（代表此产生式列表的开始符，这个开始符可多次出现在产生式的左边）占一行开始，接下来由数个以下格式的语法定义组成，每个语法定义代表一系列具有相同左侧符号的产生式的集合，每个定义之间可接受任意个数的空行。

第一行：一个字符串，代表本产生式集合左边的符号

第二行开始：每一行代表一个产生式的右侧的符号列表。每个符号之间用任意个数的空格隔开。若一行为空，则代表这是一个epsilon产生式。若一个符号包含在TokenType列表里，则这个符号会被认为是一个终结符

本集合最后一个产生式后一行：符号"%"

示例：

E （代表这个产生式列表的开始符为E）


E （定义这个产生式集合的左侧符号为E）
E PLUS T （定义一个E -> E PLUS T的产生式，PLUS是一个类型为PLUS的终结符）
T （定义一个E -> T的产生式）
% （以E为左侧的产生式集合定义完毕）


T （定义这个产生式集合的左侧符号为T）
T STAR F （定义一个F -> T STAR F的产生式，STAR是一个类型为STAR的终结符）
F （定义一个T -> F的产生式）
% （以T为左侧的产生式集合定义完毕）

F （定义这个产生式集合的左侧符号为F）
LEFT_PARENTHESIS E RIGHT_PARENTHESIS （定义一个F -> LEFT_PARENTHESIS E RIGHT_PARENTHESIS的产生式，LEFT_PARENTHESIS和RIGHT_PARENTHESIS是终结符）
IDENTIFIER （定义一个F -> IDENTIFIER的产生式）
    （定义一个F -> epsilon的epsilon产生式）
% （以F为左侧的产生式集合定义完毕）

3. 实现方法

词法定义 --> 词法DFA

语法定义 --> 语法LALR(1) DFA

输入文件 --词法DFA--> Token序列 --语法LALR(1) DFA--> 规约产生式列表

其中，词法分析器每读取一个到一个Token即暂停对输入字符的读取，转发给语法分析器进行语法分析；当语法分析器需要更多Token的时候，词法分析才继续对输入字符的读取，并不是首先生成所有的Token，再一次性交给语法LRDFA进行语法分析。

4. 假设

项目中假设只会用到以下类型的Token。若需要更多类型的Token，可在lex.internal.token.TokenType枚举类型下增加更多的Token类型。

注意，在产生式中出现Token类型列表所包含的字符串，将被认为是对应类型的终结符。字面量仅用于调试和错误报告中。

Token类型字面量备注

VOID void

INT int

RETURN return

WHILE while

IF if

ELSE else

ELLIPSIS ...

EQUAL ==

ASSIGN =

SEMICOLON ;

STAR *

OR_OR

LEFT_BRACE...

剩余内容已隐藏

查看完整文章以阅读更多

查看完整文章

ddadaal.me

ddadaal's personal website

马上订阅 ddadaal.me RSS 更新: https://ddadaal.me/rss.xml

正则语法分析器和LALR(1)词法分析器

2018年11月19日 13:37

compiling课内

0. 说明

项目是放在一个repo的子文件夹里的，目录是：https://github.com/ddadaal/Homework/tree/master/Compiler/CompilerLab

编译原理实验报告

1. 目标

2. 内容描述

本实验提供了以下内容：

一个Intellij IDEA格式的Java项目，包含了目标中提到的词法分析器、语法分析器以及对应分析器的一些测例。
能被分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式描述
以龙书上例题4.31为依据的输入文件、输出文件、myl词法定义文件和myy语法定义文件，并提供了对应的测例
一个C语言子集的输入文件、输出文件、myl词法定义文件和myy语法定义文件。同时还提供了与其中myl和myy等价的flex/bison定义文件以及对应的一些工具程序。提供的词法定义和语法定义已经经过flex和bison测试可以完整无错误的解析提供的输入文件。

2.1 词法定义文件格式myl

一个myl包含数个以下格式的词法定义，每个定义之间可接受任意个数的空行。

第一行：正则表达式的字符串
第二行：对应的TokenType的字符串

其中，正则表达式支持以下元素：

字符字面量
闭包（*）
并集（|）
覆写优先级的括号（(, )）
escaped字符(\n, \t, \b，", \ (空格，表示一个空格), \+, \*, \(, \), \r)

扩展支持：

方括号([])

方括号内部出现的元素之间会通过并集|连接，可与字符类配套使用。

例如：[ac\n]等价于(a|c|\n)

字符类（-），只能出现在方括号中

在ASCII表中，-前面的符号和后面的符号之间的所有符号会通过并集|连接。

例如：[a-d]等价于(a|b|c|d)

例如：[\n\ba-d_]等价于(\n|\b|(a|b|c|d)|_)

示例：

\+
PLUS （定义一个正则表达式为\+，对应到PLUS类型的Token的匹配规则，）

\*
STAR（定义一个正则表达式为\*，对应到STAR类型的token的匹配规则）

\(
LEFT_PARENTHESIS

\)
RIGHT_PARENTHESIS

[a-zA-Z]([0-9a-zA-Z_])*
IDENTIFIER （定义一个正则表达式为[a-zA-Z]([0-9a-zA-Z_])*（即以字母开头，后面跟任意个数的数字、字母或下划线），对应到IDENTIFIER类型的token转换规则）

[\ \n\r]
IGNORED （定义空格、空行或\r字符都被匹配到IGNORED类型的token的转换规则）

2.2 语法分析文件格式myy

第一行：一个字符串，代表本产生式集合左边的符号

第二行开始：每一行代表一个产生式的右侧的符号列表。每个符号之间用任意个数的空格隔开。若一行为空，则代表这是一个epsilon产生式。若一个符号包含在TokenType列表里，则这个符号会被认为是一个终结符

本集合最后一个产生式后一行：符号"%"

示例：

E （代表这个产生式列表的开始符为E）


E （定义这个产生式集合的左侧符号为E）
E PLUS T （定义一个E -> E PLUS T的产生式，PLUS是一个类型为PLUS的终结符）
T （定义一个E -> T的产生式）
% （以E为左侧的产生式集合定义完毕）


T （定义这个产生式集合的左侧符号为T）
T STAR F （定义一个F -> T STAR F的产生式，STAR是一个类型为STAR的终结符）
F （定义一个T -> F的产生式）
% （以T为左侧的产生式集合定义完毕）

F （定义这个产生式集合的左侧符号为F）
LEFT_PARENTHESIS E RIGHT_PARENTHESIS （定义一个F -> LEFT_PARENTHESIS E RIGHT_PARENTHESIS的产生式，LEFT_PARENTHESIS和RIGHT_PARENTHESIS是终结符）
IDENTIFIER （定义一个F -> IDENTIFIER的产生式）
    （定义一个F -> epsilon的epsilon产生式）
% （以F为左侧的产生式集合定义完毕）

3. 实现方法

词法定义 --> 词法DFA

语法定义 --> 语法LALR(1) DFA

输入文件 --词法DFA--> Token序列 --语法LALR(1) DFA--> 规约产生式列表

4. 假设

项目中假设只会用到以下类型的Token。若需要更多类型的Token，可在lex.internal.token.TokenType枚举类型下增加更多的Token类型。

注意，在产生式中出现Token类型列表所包含的字符串，将被认为是对应类型的终结符。字面量仅用于调试和错误报告中。

Token类型字面量备注

VOID void

INT int

RETURN return

WHILE while

IF if

ELSE else

ELLIPSIS ...

EQUAL ==

ASSIGN =

SEMICOLON ;

STAR *

OR_OR

LEFT_BRACE...

剩余内容已隐藏

查看完整文章以阅读更多

查看完整文章

ddadaal.me

ddadaal's personal website

马上订阅 ddadaal.me RSS 更新: https://ddadaal.me/rss.xml

正则语法分析器和LALR(1)词法分析器

2018年11月19日 13:37

compiling课内

0. 说明

项目是放在一个repo的子文件夹里的，目录是：https://github.com/ddadaal/Homework/tree/master/Compiler/CompilerLab

编译原理实验报告

1. 目标

2. 内容描述

本实验提供了以下内容：

一个Intellij IDEA格式的Java项目，包含了目标中提到的词法分析器、语法分析器以及对应分析器的一些测例。
能被分析器所解析的词法定义文件（.myl）和语法定义文件（.myy）的格式描述
以龙书上例题4.31为依据的输入文件、输出文件、myl词法定义文件和myy语法定义文件，并提供了对应的测例
一个C语言子集的输入文件、输出文件、myl词法定义文件和myy语法定义文件。同时还提供了与其中myl和myy等价的flex/bison定义文件以及对应的一些工具程序。提供的词法定义和语法定义已经经过flex和bison测试可以完整无错误的解析提供的输入文件。

2.1 词法定义文件格式myl

一个myl包含数个以下格式的词法定义，每个定义之间可接受任意个数的空行。

第一行：正则表达式的字符串
第二行：对应的TokenType的字符串

其中，正则表达式支持以下元素：

字符字面量
闭包（*）
并集（|）
覆写优先级的括号（(, )）
escaped字符(\n, \t, \b，", \ (空格，表示一个空格), \+, \*, \(, \), \r)

扩展支持：

方括号([])

方括号内部出现的元素之间会通过并集|连接，可与字符类配套使用。

例如：[ac\n]等价于(a|c|\n)

字符类（-），只能出现在方括号中

在ASCII表中，-前面的符号和后面的符号之间的所有符号会通过并集|连接。

例如：[a-d]等价于(a|b|c|d)

例如：[\n\ba-d_]等价于(\n|\b|(a|b|c|d)|_)

示例：

\+
PLUS （定义一个正则表达式为\+，对应到PLUS类型的Token的匹配规则，）

\*
STAR（定义一个正则表达式为\*，对应到STAR类型的token的匹配规则）

\(
LEFT_PARENTHESIS

\)
RIGHT_PARENTHESIS

[a-zA-Z]([0-9a-zA-Z_])*
IDENTIFIER （定义一个正则表达式为[a-zA-Z]([0-9a-zA-Z_])*（即以字母开头，后面跟任意个数的数字、字母或下划线），对应到IDENTIFIER类型的token转换规则）

[\ \n\r]
IGNORED （定义空格、空行或\r字符都被匹配到IGNORED类型的token的转换规则）

2.2 语法分析文件格式myy

第一行：一个字符串，代表本产生式集合左边的符号

第二行开始：每一行代表一个产生式的右侧的符号列表。每个符号之间用任意个数的空格隔开。若一行为空，则代表这是一个epsilon产生式。若一个符号包含在TokenType列表里，则这个符号会被认为是一个终结符

本集合最后一个产生式后一行：符号"%"

示例：

E （代表这个产生式列表的开始符为E）


E （定义这个产生式集合的左侧符号为E）
E PLUS T （定义一个E -> E PLUS T的产生式，PLUS是一个类型为PLUS的终结符）
T （定义一个E -> T的产生式）
% （以E为左侧的产生式集合定义完毕）


T （定义这个产生式集合的左侧符号为T）
T STAR F （定义一个F -> T STAR F的产生式，STAR是一个类型为STAR的终结符）
F （定义一个T -> F的产生式）
% （以T为左侧的产生式集合定义完毕）

F （定义这个产生式集合的左侧符号为F）
LEFT_PARENTHESIS E RIGHT_PARENTHESIS （定义一个F -> LEFT_PARENTHESIS E RIGHT_PARENTHESIS的产生式，LEFT_PARENTHESIS和RIGHT_PARENTHESIS是终结符）
IDENTIFIER （定义一个F -> IDENTIFIER的产生式）
    （定义一个F -> epsilon的epsilon产生式）
% （以F为左侧的产生式集合定义完毕）

3. 实现方法

词法定义 --> 词法DFA

语法定义 --> 语法LALR(1) DFA

输入文件 --词法DFA--> Token序列 --语法LALR(1) DFA--> 规约产生式列表

4. 假设

项目中假设只会用到以下类型的Token。若需要更多类型的Token，可在lex.internal.token.TokenType枚举类型下增加更多的Token类型。

注意，在产生式中出现Token类型列表所包含的字符串，将被认为是对应类型的终结符。字面量仅用于调试和错误报告中。

Token类型	字面量	备注
VOID	void
INT	int
RETURN	return
WHILE	while
IF	if
ELSE	else
ELLIPSIS	...
EQUAL	==
ASSIGN	=
SEMICOLON	;
STAR	*
OR_OR
LEFT_BRACE... 剩余内容已隐藏查看完整文章以阅读更多查看完整文章