Python-编译原理算法

[TOC]

编译原理课程作业

• 词法分析器
• LL1分析(消去左递归、构造FIRST\FOLLOW集合、模拟)
• 递归下降分析
• 算法优先分析

项目地址源代码

https://github.com/Aczy156/Compiling-Principle-Work

项目结构

data

• Grammer_for_ll1_and_RD.txt，是存放用于实验二预测分析法和实验三递归下降分析文法的测试文法
• Grammer_for_OF.txt，是存放用于实验四算符优先文法的测试文法。

MultiAnalysis

• LL1_analysis.py是LL1分析法的整体过程。
• RecursiveDescent_analysis.py是递归下降分析的整体过程。
• OperatorFirst_analysis.py是算符优先文法的整体分析过程。

tools

[在MultiAnalysis中的各种文法中多次使用，所以提取出来子模块，放进工具中来模块化管理]

• Draw_Grammer.py，利用python中prettytable来专门做文法的可视化。
• Eliminate_Left_Recursion.py，利用消除左递归算法来专门处理对于自上而下的文法(例如实验二中的预测分析文法和实验三的递归下降文法)的左递归的问题。
• Extract_Common_Factors.py，利用LCP(最长公共前缀)来提取公因子并消除。

数据结构

(命名基本保持一致，除了在一些情境中要利用python deepcopy深备份一份或者要进行更改会命名为new_grammer/new_vn等等)：

• 文法grammer：文法在通过预处理过后，通过python中的数据结构dictionary(dict、字典)来映射，例如{‘E’: [‘E+T’, ‘T’], ‘T’: [‘T*F’, ‘F’], ‘F’: ['(E)', ‘i’]}，用来表示通过数据预处理之后的最基本的算术表达式文法。
• 非终结符vn：非终结符通过list来盛放。例如[‘E’, ‘T’, ‘F’]，用来表示通过数据预处理之后的最基本的算术表达式文法的非终结符。
• 终结符vt：终结符通过list来盛放。例如 ['(', ‘)', ‘i’, ‘+’, ‘*', ‘#']，用来表示通过数据预处理之后的最基本的算术表达式文法的非终结符。