https://github.com/McFly-byte/compiler/tree/master
- 课程设计总览
- 课程设计要求
- 创建一个词法分析程序，该程序支持分析常规单词。
- 创建一个使用 LL(1) 方法或 LR(1) 方法的语法分析程序。
- 项目基本内容
- 词法分析器
- 语法分析器
- 开发环境
- 语言：C++
- 硬件环境：Windows10 + DevC++5.11
- 项目结构
- 文件说明：
- 项目结构：
- 词法分析器（Lexer）
- 实现原理
- 识别类型
- 正规文法
- 重要类与结构定义
- NFA 不确定的有穷自动机
- LA 词法分析
- isEquallALL 比较类（在map中根据second找key）
- 重要函数
- 运行结果
- 输入源程
- 运行时相关信息
- 运行结果
- 语法分析器（Parser）
- 实现原理
- 原理
- 文法
- 重要类与结构定义
- LR（0）
- LR（1）
- 重要函数
- 运行结果
- 运行时相关信息
- 运行结果
a) 输入：一个文本文档，包括一组 3º型文法（正规文法）的产生式。
b) 输出：一个源代码文本文档，包含一组需要识别的字符串（程序代码）。
c) 要求：词法分析程序可以准确识别:科学计数法形式的常量（如 0.314E+1），复数常量（如10+12i），可检查整数常量的合法性，标识符的合法性（首字符不能为数字等），尽量符合真实常用高级语言要求的规则。
a) 输入：包含 2º型文法（上下文无关文法）的产生式集合的文本文档；任务 1 词法分析程序输出的（生成的）token 令牌表。
b) 输出：YES 或 NO（源代码字符串符合此 2º型文法，或者源代码字符串不符合此 2º型文法）；错误提示文件，如果有语法错标示出错行号，并给出大致的出错原因。
a) 输入：自定义正规文法文件、程序源代码
b) 输出：Token串（三元组）
c) 流程：读入正规文法，生成对应NFA，确定化NFA，根据生成的DFA对输入源程序代码进行分析，产生Token串
a) 输入：自定义2型文法文件、词法分析产生的Token串
b) 输出：LR（1）分析信息（项目集族、状态信息等）、错误信息、分析结果
c) 流程：
i) 第一步，读入2型文法，构造项目族规范集，根据LR（1）分析法产生对应的DFA、Action表、Goto表。
ii) 第二步，读入Token串，根据LR（1）的产物进行语法分析。
a) 文件夹
i) Compiler 项目文件夹
ii) Lexer 子项目词法分析器
iii) Parser 子项目语法分析器
b) .cpp/.h
i) LR LR（1）分析法
ii) NFA 不确定、确定的有穷自动机
iii) Op 将复杂的文法描述转换成字母符号产生式
c) .txt（输入、输出文件）
i) Input.txt/output.txt: 输入、输出测试
ii) Regular grammar.txt: 正规文法
iii) Source code.txt: 源程序代码
iv) Lexer.txt: Token（行号、内容、类别）序列
v) Describe.txt:语法描述
vi) 2NF grammar.txt: 语法对应2型文法
vii) Parser.txt:程序输出
a) Compiler
b) Lexer
c) Parser
| 类型 | 具体说明 |
|---|---|
| 关键字 | “if”、“then”、“else”、“bool”、“char”、“int”、“double”、“const”、“while”、“do”、“begin”、“end” |
| 标识符 | 可以由数字、字母、下划线组成。 |
| 常量 | 可以识别整数、小数、科学计数法、复数 |
| 运算符 | 单目运算符：“=”、“+”、“-”、“>”、“<”、“*”、“/”、“%” |
| 运算符 | 双目运算符：“==”、“>=”、"<="等 |
| 界符 | “;”、“(”、“)”、“{”、“}”、“,” |
说明：
i) 内容类别由正规文法第一行产生式右部确定：Token-标识符、Operator-运算符、Separator-界符、Constant-常量、Key-关键字
ii) 根据此正规文法，可识别“识别类型”中全部类别
iii) 文法已由符号代替非终结符，并作正规化，该步骤独立与机器手动完成
iv) 程序读入时自动跳过“//”注释之后该行的内容
class LA
LA(); void analysis( NFA& nfa, string file3, string file2 ); void read_next_VT( char ch, NFA& nfa, string file2 ); void output( int tag, NFA& nfa, string file2 );
};
isEquallALL 比较类（在map中根据second找key）class isEqualALL
{
public:
explicit isEqualALL(char c) : ch© {}
bool operator() (const std::pair
return element.second == ch;
}
private:
const char ch;
};
| 函数定义 | 注释 |
|---|---|
| void NFA::nfa_2_dfa() | |
| void NFA::cope_line( string line ) | |
| void NFA::cope_formula( string formula ) | |
| void NFA::e_closure( string status, vector& T ) | |
| void NFA::vt_move( char vt, vector V, vector& T ) | |
| string NFA::get_first_VN( string formula ) | |
| string NFA::get_next_VN( string & formula ) | |
| string NFA::get_next_VT( string & formula ) | |
| void LA::analysis( NFA& nfa, string file3, string file4 ) | |
| void LA::read_next_VT( char ch, NFA& nfa, string file4 ) |
a) NFA信息
b) NFA 状态-弧 （部分）
c) DFA信息
d) DFA 状态-弧
运行结果（部分截图）
先根据2型文法，利用LR（1）分析法构造项目集，进而得到DFA、Action表和Goto表。再利用词法分析的结果进行语法分析，输出相应信息
文法对应2型文法
说明：
i) 语法由describle.txt给出，由op转为2型文法并输出到2NF grammar.txt中。
ii) 每个大写字母对应一个或一类非终结符，每个小写字母对应一个或一类终结符。
iii) 最终分析的结果再由文件最后一行字典转换为字符对应的状态
class LR1 : public LR
{
public:
map
map
void generate_firstset(); bool contains( string a, string b ); string first( string remaider, string lookahead ); virtual void input( string File ); void analysis( string FileIn, string FileOut ); void build_DFA(); void build_table( vector& Collections ); void enclosure( clcn& C ); int verify_conflict( clcn C ); void print_state( clcn C );
}；
重要函数void LR::collection_2_dfa()
void LR::build_table( vector
void LR::enclosure( vector& Closure )
int LR::verify_conflict( vector Closure )
void LR::report( int error )
void LR::input( string File )
void LR1::analysis( string FileIn, string FileOut )
void LR1::generate_firstset()
void LR1::print_state( clcn C )
string LR1::first( string remainder, string lookahead )
void LR1::build_DFA()
string UTF8ToGB(const char* str);
void turn_to_2NF( string In, string Out );
*具体实现见代码包
a) 各项目集规范族内容（部分截图）
序号即代表状态号，从结果来看，共186个状态
b) DFA状态-弧 （部分截图）
c) Action表
d) Goto表 （部分截图）
运行结果将输入远程序改写后（去掉while-do语句的后半部分），重新执行：
输出
