[C++知识库]编译原理课设 词法分析 语法分析 C++实现

https://github.com/McFly-byte/compiler/tree/master

课程设计总览

课程设计要求

创建一个词法分析程序，该程序支持分析常规单词。

a) 输入：一个文本文档，包括一组 3o型文法（正规文法）的产生式。
b) 输出：一个源代码文本文档，包含一组需要识别的字符串（程序代码）。
c) 要求：词法分析程序可以准确识别:科学计数法形式的常量（如 0.314E+1），复数常量（如10+12i），可检查整数常量的合法性，标识符的合法性（首字符不能为数字等），尽量符合真实常用高级语言要求的规则。

创建一个使用 LL(1) 方法或 LR(1) 方法的语法分析程序。

a) 输入：包含 2o型文法（上下文无关文法）的产生式集合的文本文档；任务 1 词法分析程序输出的（生成的）token 令牌表。
b) 输出：YES 或 NO（源代码字符串符合此 2o型文法，或者源代码字符串不符合此 2o型文法）；错误提示文件，如果有语法错标示出错行号，并给出大致的出错原因。

项目基本内容

词法分析器

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）的产物进行语法分析。

开发环境

语言：C++

硬件环境：Windows10 + DevC++5.11

项目结构

文件说明：

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

词法分析器（Lexer）

实现原理

识别类型

正规文法

说明：
i) 内容类别由正规文法第一行产生式右部确定：Token-标识符、Operator-运算符、Separator-界符、Constant-常量、Key-关键字
ii) 根据此正规文法，可识别“识别类型”中全部类别
iii) 文法已由符号代替非终结符，并作正规化，该步骤独立与机器手动完成
iv) 程序读入时自动跳过“//”注释之后该行的内容

重要类与结构定义

NFA 不确定的有穷自动机

LA 词法分析

class LA /* Lexical Analysis /
{
public:
ofstream fout;
string line; / 输入行 /
string word; / 当前处理串 /
string T; / 当前状态 /
int index; / 当前状态对应List中下标 /
int id; / 输出编号 */

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<string, char>& element) const {
return element.second == ch;
}
private:
const char ch;
};

重要函数

运行结果

输入源程

运行时相关信息

a) NFA信息

b) NFA 状态-弧 （部分）

c) DFA信息

d) DFA 状态-弧

运行结果

（部分截图）

语法分析器（Parser）

实现原理

原理

先根据2型文法，利用LR（1）分析法构造项目集，进而得到DFA、Action表和Goto表。再利用词法分析的结果进行语法分析，输出相应信息

文法

对应2型文法

说明：
i) 语法由describle.txt给出，由op转为2型文法并输出到2NF grammar.txt中。
ii) 每个大写字母对应一个或一类非终结符，每个小写字母对应一个或一类终结符。
iii) 最终分析的结果再由文件最后一行字典转换为字符对应的状态

重要类与结构定义

LR（0）

LR（1）

class LR1 : public LR
{
public:
map<char,string> First; /* 每个非终结符的First集的集合 */
map<string,char> Dic;

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<clcn>& Collections ); 
void enclosure( clcn& C );
int  verify_conflict( clcn C );
void print_state( clcn C );  

}；

重要函数

void LR::collection_2_dfa()
/* 根据项目集规范组得到DFA、Action、Goto */

void LR::build_table( vector<vector >& States )
/* 根据DFA构造Action表和Goto表 /
/ 规定0状态遇初态结束 */

void LR::enclosure( vector& Closure )
/* 把闭包根据规则扩充，不改变其状态 */

int LR::verify_conflict( vector Closure )
/* 检测闭包中是否存在冲突 */

void LR::report( int error )
/* 根据error的类型报告错误 */

void LR::input( string File )
/* 输入2型文法产生式 /
/ 因为是2型文法，故规定每个Vt、Vn长度都为1 /
/ Production第0位是产生式左部，后面是产生式右部 */

void LR1::analysis( string FileIn, string FileOut )
/* 读入词法分析结果，进行语法分析，输出 */

void LR1::generate_firstset()
/* 生成每个非终结符的First集的集合 */

void LR1::print_state( clcn C )
/* 输出项目集族 */

string LR1::first( string remainder, string lookahead )
/* 输入项目分隔符右边部分以及该项目向前搜索符，求给出字串的first集 */

void LR1::build_DFA()
/* 重写LR1中项目集规范族的构造, 产生DFA、Action、Goto */

string UTF8ToGB(const char* str);
/* 读入一行包含中文字符的字符串，使其能够存入map中不产生乱码 */

void turn_to_2NF( string In, string Out );
/* 逐字符处理语法，生成2NF */
*具体实现见代码包

运行结果

运行时相关信息

a) 各项目集规范族内容（部分截图）
序号即代表状态号，从结果来看，共186个状态

b) DFA状态-弧 （部分截图）

c) Action表

d) Goto表 （部分截图）

运行结果

将输入远程序改写后（去掉while-do语句的后半部分），重新执行：

输出

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖