# LR1Generator **Repository Path**: dozenzy/lr1-generator ## Basic Information - **Project Name**: LR1Generator - **Description**: LR1分析表生成器，对于冲突项会进行提示，可以根据提示来解决冲突。 - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-07-20 - **Last Updated**: 2024-07-20 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # LR1Generator ### 背景前些时间，在编译原理实验中，要求我们编写一个简单的语法分析器，需要兼顾语义分析，于是选择了LR(1)分析进行实现。但在构造LR(1)分析表的时候发现，对于稍复杂一些的文法，项目集族会变得很庞大，手工进行分析、构造分析表耗时会很长并且不能保证正确性。因此到网上搜索了LR(1)分析表的自动构造，但是没有找到能满足我需求的，因此自己花了一天时间写了一个程序生成分析表后应付完成了作业。不过感觉不太满意，于是又花了点时间研究修复了一点bug之后决定交给网友们拷打。在此需要感谢@Vizdl前辈的博客给予我的灵感，本程序的输入输出格式均参考自他的博客[LR(1)语法分析器生成器(生成Action表和Goto表)java实现(一)-CSDN博客](https://blog.csdn.net/RT_776/article/details/103710378)，在此也指出这篇博客提供的程序的一点不足，在面临一些空字产生式时，无法提供正确的分析表；如果文法存在二义，如存在移进-归约冲突或归约归约冲突，这在一些表达式文法中是非常常见的，这时也无法提供提示和修正意见。因此我重新写了一个LR(1)的分析表生成程序。程序可以从我的仓库获取，也可以直接复制文末代码。 ### 使用指南使用时需准备两个txt文件：productions.txt，TSymbols.txt 其中production.txt中填写产生式，填写时遵循以下规则： 1. 每行填写一条，可以用直竖并列多个右部， 2. 非终结符使用左右尖括号进行包裹，终结符使用英文双引号进行包裹 3. 产生式左部和右部使用"::="进行连接 4. 每条产生式末加上英文分号 5. ==由于左右尖括号、英文双引号、英文分号已被用作特殊符号，要在终结符使用这些符号时请使用中文或其他标记符号进行代替。== 6. ==空字已被预先定义，如若需要使用空字，请使用"ε"。== 7. 所有空白都是无效符号，在处理时会被脱除，空白终结符(不包含空字ε)也如此。 8. ==请自行对文法进行拓广，文法的开始符号对应的产生式只能有一个右部，否则会出现问题。== TSymbols.txt中填写所有终结符，生成的分析表中非终结符项将会按照填写顺序进行输出。下面的样例提供了一个简单语言的文法，该样例包含移进归约冲突，下面我会展示如何依照程序给出的提示和建议解决冲突。 ### 输入样例 productions.txt样例： ``` start : ; ::= ; ::= "ε"||; ::= |||; ::= "id" "分号"; ::= "bool"|"int"; ::= "id" ":=" "分号"; ::= "+" | "-" | "(" ")"| ; ::= "*" | "/" | "id" | "digit"; ::= "if" "then" "分号"| "if" "then" "else" "分号"; ::= "or" | "(" ")"| ; ::= "and" |; ::= "id"|"true"|"false"| "<" | ">" | "=" | "not" ; ::= "while" "do" "分号"; ::= "begin" "end"; ::= "ε"; ::= "ε"; ``` TSymbols.txt样例： ``` program begin end bool int if then else do while true false and or not digit + - * / ( ) = > < 分号 , := : # id ``` ### 输出结果及分析运行程序后会输出两个文件，一个是productionOrder.txt，另一个是lr1Table.txt。 productionOrder.txt输出了仅包含一个右部的产生式顺序。 lr1Table.txt输出的是分析表的主体。控制台会输出冲突提示。将输入样例输入后会得到有冲突的结果。 lr1Table.txt输出部分结果如下： ``` Action表如下 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …… 0 err err err s11 s12 s9 err err err s10 err err err err err …… 1 err err err r37 r37 r37 err err err r37 err err err err err …… …… ``` 控制台会如此提示： ``` 文法存在移入归约冲突，分析表可能不正确，冲突位于分析表第0行,第4列，默认选择了移入方案，归约方案有r2 文法存在移入归约冲突，分析表可能不正确，冲突位于分析表第0行,第5列，默认选择了移入方案，归约方案有r2 文法存在移入归约冲突，分析表可能不正确，冲突位于分析表第0行,第6列，默认选择了移入方案，归约方案有r2 …… ``` 出现冲突时，说明文法是有二义的，以第一条提示为例，产生移入归约冲突时，我们要先看归约方案的产生式，来获知此时的分析栈状况以及了解归约方案的文法意义。它提示此时的归约方案还有r2，我们查看productionOrder.txt，第二条产生式为` ::= "ε"`，这条产生式说的是语句块内容可以为空，此时再查看TSymbol.txt，第4列对应的终结符为`bool`，说明此时遇到的字符并不是语句块的结束符`end`，因此此时并不应当进行归约，保持默认的移入方案即可。再举一个例子： lr1Table.txt输出部分结果如下： ``` Action表如下 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 …… …… 43 err err r19 r19 r19 r19 err r19 r19 r19 r19 err err err err …… ``` 控制台有如此提示： ``` 文法存在归约归约冲突，分析表可能不正确，冲突位于分析表第43行,第22列，其余归约方案还有r28 ``` 产生归约归约冲突时需要对比两个方案的产生式，结合其他列的方案情况来判断当前应采用哪个产生式，归约归约冲突可能较难排解，出现较多归约归约冲突时请考虑修改你的文法。先查得19号产生式为` ::= "id"`，这条产生式说的是算术表达式的因子可以是某个变量，28号产生式为` ::= "id"`，这条产生式说的是布尔表达式的因子可以是某个变量。两者的区别在于表达式的类型，我们需要根据分析表中其他列的情况判断当前是在准备哪一个表达式，由于其他列都是根据19号产生式归约，并且，考虑到该文法中布尔表达式之后不会出现`+`，`-`，`*`，`/`等符号，而该状态下对应的17、18、19、20列并非err，所以不会是布尔表达式，因此保持归约方案r19。再看一个需要修改的例子： ``` Action表如下 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 …… …… 105 err err s52 s53 err err err err r14 r14 r14 err err err err …… ``` 控制台有如此提示： ``` 文法存在移入归约冲突，分析表可能不正确，冲突位于分析表第105行,第17列，默认选择了移入方案，归约方案有r14 ``` 移入规约冲突先找归约方案产生式，13号产生式为` ::= "-" `，说明为算术表达式的项可以通过减号相连来拓展表达式，17号终结符为`+`。如果采用移入方案，不进行归约，就会使得表达式的项不断被移入，直到表达式结束，然后从尾部开始向前归约，说明此时符号的结合性是右结合的。可能你已经发现问题了，考虑这样一个表达式：1-2+3，如果采用右结合，也就是2+3先计算，得到5，表达式等价于1-5，结果错误了。因此在算术表达式中，应当让算符是左结合的。体现在分析表中就应当是尽早归约，而非不断移入，等待归约。因此，需要将移入方案修改为归约方案。 ### 参考文献 [1]陈火旺,刘春林,谭庆平,赵克佳,刘越.程序设计语言编译原理(第3版)[M].北京:国防工业出版社,2000. [2][LR(1)语法分析器生成器(生成Action表和Goto表)java实现(一)-CSDN博客](https://blog.csdn.net/RT_776/article/details/103710378)