基于Python实现的语法分析.zip

# 实验2：语法分析 ## 需求分析 1. 生成LR(1)分析中用到的action和goto表。 2. 采用LR(1)对类C语言中的基本语句进行句法分析。 3. 对源程序中存在语法错误报错。 ## 文法设计 1.声明语句 ```python Defination -> Data id Data -> Type | Data [ const ] Type -> int | float | bool | id Struct -> struct id { Statement } Statement -> Defination ; | Defination ; Statement Function -> Data id ( Parameter ) { Process } Parameter -> epsilon | Defination | Defination , Parameter Process -> Module Return Return -> return id Index ; | epsilon ``` 2.表达式及赋值语句 ```python Assignment -> id Index = Value Value -> Value + Value | Value - Value | Value * Value | Value / Value | Call Value -> - Value Value -> ( Value ) Value -> const | id Index Index -> [ Value ] Index | epsilon ``` 3.分支语句&循环语句 ```python Control -> If | IfElse | While If -> if ( Condition ) { Module } IfElse -> if ( Condition ) { Module } else { Module } While -> while ( Condition ) { Module } Condition -> Condition and Condition | Condition or Condition | not Condition | ( Condition ) | Value Relop Value | true | false Relop -> < | <= | == | != | > | >= ``` 4.过程调用语句 ```python Call -> id ( Transmit ) Transmit -> epsilon | Value | Value , Transmit ``` 其中空格分隔单个字符，epsilon表示空串，大写开头的单词表示非终结符。 ## 系统设计 系统概要设计： 功能模块图如下  系统详细设计： 1. 核心数据结构的设计 ```python class Item(object): """生成action, goto表时的单个转移语法 """ def init(self, nonterminal: str, grammar: List[str], character: str): self.nonterminal = nonterminal self.grammar = grammar self.__character = character def nonterminal(self): return self.__nonterminal def grammar(self): return self.__grammar def character(self): return self.__character def operate_position(self): for i in range(len(self.grammar)): if self.grammar[i] == '@': return i def eq(self, other): if not isinstance(other, Item): return False if self.nonterminal != other.nonterminal(): return False if self.character != other.character(): return False grammar = other.grammar() if len(grammar) != len(self.__grammar): return False for i in range(len(grammar)): if grammar[i] != self.__grammar[i]: return False return True def hash(self): return hash('[' + self.nonterminal + '->' + self.grammar + ',' + self.__character + ']') ``` 2. 主要功能函数说明 ```python def get_closure(items: List[Item], grammar: Dict[str, List[List[str]]], first: Dict[str, List[str]]) -> List[Item]: '''根据项目集和文法构造闭包 Args: items: 项目集 grammar: 文法 first: first集合 Returns: 相应闭包 ''' def get_goto(items: List[Item], grammar: Dict[str, List[List[str]]], char: str, first: Dict[str, List[str]]) -> List[Item]: '''计算一个项目集的GOTO集合 Args: items: 项目集 grammar: 文法 char: 文法符号 first: first集合 Returns: GOTO集合 ''' def get_items(grammar: Dict[str, List[List[str]]], start: str): '''计算一个文法的LR(1)项集族 以@表示处理位置，$表示句子结尾，以Start表示开始 Args: grammar: 文法 Start: 开始符号 Returns: 项集族 ''' def get_action_and_goto(items: List[List[Item]], grammar: Dict[str, List[List[str]]], start: str): '''计算项集族对应的ACTION和GOTO表 Args: items: 项集族 grammar: 文法 start: 开始符号 Returns: ACTION表 GOTO表 ''' def analyse(words: List[Word], action: Dict[int, Dict[str, str]], goto: Dict[int, Dict[str, str]]): '''根据action和goto表构造语法分析树 采用恐慌模式处理语法错误 Args: words: 词法分析结果，格式为value (class, value) action: action表 goto: goto表 Returns: 语法分析树，格式为[{'word': ..., 'child': [id1, id2, ...], 'id': ...}] 其中id为节点在返回列表中的角标 ''' ``` 3. 程序核心部分的程序流程图  ## 系统实现及结果分析 1. 系统实现过程中遇到的问题 教材中未提及自底向上文法分析中，生成转移表时，遇到ε该如何处理。 为此，在生成闭包时，若语法包含空串，则添加转移语法”A->.” 2. 输出该句法分析器的分析表 由于分析表文件过大，参看附件中data/table文件夹中的文件。 3. 针对测试程序输出其句法分析结果 ```python Module (35) Function (4) Data (0) Type (0) int (0) id : sum (0) ( (0) Parameter (0) Defination (0) Data (0) Type (0) float (0) id : a (0) ``` 截取部分输出如上所示，其中每一行最后为源代码中的行号，对于标识符id和常数const，后面会紧跟实际的名称或数值。 4. 输出针对此测试程序对应的语法错误报告 int float = 89; int sum1; 对于上述错误，程序采用恐慌模式，进行删除float、=、89、;、int，直到合乎语法。 Syntax error at Line [15]: illegal float Syntax error at Line [15]: illegal = Syntax error at Line [15]: illegal const Syntax error at Line [15]: illegal ; Syntax error at Line [17]: illegal int 5. 对实验结果进行分析 实验结果正确，与预期结果相符。