加强单位门户网站建设的通知,app开发公司哪个公司好,如何去做电商平台,崇信门户网个人留言图源#xff1a;文心一言
编译原理习题整理~#x1f95d;#x1f95d;
作为初学者的我#xff0c;这些习题主要用于自我巩固。由于是自学#xff0c;答案难免有误#xff0c;非常欢迎各位小伙伴指正与讨论#xff01;#x1f44f;#x1f4a1;
第1版#xff1a;自…
图源文心一言
编译原理习题整理~
作为初学者的我这些习题主要用于自我巩固。由于是自学答案难免有误非常欢迎各位小伙伴指正与讨论
第1版自己的解题与AI老师的判卷~
编辑梅头脑
审核文心一言
题源龙书《编译原理》 Alfre V.Aho 等著 赵建华 等译 目录
参考答案
练习2.3.1
练习2.3.2
练习2.3.3
练习2.3.4
结语 参考答案 fool2fish (Zhouxuan Yang) 博文dragon-book-exercise-answers - GitCode 练习2.3.1
题目 构建一个语法制导翻译方案该方案把算术表达式从中缀表示方式翻译成运算符在运算分量之前的前缀表达方式。例如-xy是表达式 x-y 的前缀表示法。给出输入 9-52 和 9-5*2 的注释分析树。 答题 产生式 expr → expr { ( | -) term }
term → factor { (* | /) factor }
factor → ( expr ) | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 语义规则 expr → {print ( | -)} expr { ( | -) term }
term → {print (* | /)} factor { (* | /) factor }
factor → ( expr ) | {print (digit)} digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 注释分析树(这个小问好像找不到参考答案) AI审核
1我曾问过AI它习惯将第一行写为expr → term { ( | -) term }这实际与教材中书写的expr → expr { ( | -) term }不同为什么不写为后者呢 第一行产生式 expr → expr { ( | -) term } 。这种表示方法采用了左递归的形式意味着一个表达式可以是一个更复杂的表达式后跟一个由加法或减法运算符和另一个项组成的序列。然而左递归形式对于某些解析技术如自顶向下的解析器如递归下降解析器来说可能会导致问题因为它们可能无法有效地处理这种直接或间接的无限递归情况。为了避免这些问题通常会使用等价的右递归形式来重写产生式如下所示 expr → term { ( | -) term } 在这个右递归版本中expr 以一个 term 开始后面可以跟零个或多个由加法或减法运算符和另一个 term 组成的序列。这种形式更适合于自顶向下的解析算法因为它保证了解析过程在有限的步骤内会终止。在您提供的原始问题中没有特别指明必须使用左递归还是右递归形式因此两者在描述算术表达式的语法结构时都是有效的。但是从实现解析器的角度来看选择右递归形式通常是更可取的做法因为它与更广泛使用的解析算法兼容。因此即使第一行写成 expr → expr { ( | -) term } 在语法上是正确的但考虑到解析器的实现通常更倾向于使用右递归形式 expr → term { ( | -) term }。 知识扩展 树是什么鬼先序遍历又是什么鬼数据结构05树与二叉树[C]-CSDN博客中缀转后缀的C代码数据结构03栈、队列和数组-CSDN博客 练习2.3.2
题目 构建一个语法制导翻译方案该方案把算术表达式从后缀表达式翻译成中缀表达式。给出输入 95-2* 和 95*2- 的注释分析树。 争议 本题解题过程可能有误可能的争议点如下欢迎小伙伴指导与讨论~问题1 按照我看书的理解表达式可能是这样的 产生式expr → expr term这个用于描述中缀表达式语义规则expr expr.t || term.t || 这个用于描述后缀表达式语义动作expr → expr term {print()}这个用于将中缀表达式翻译为后缀其中的{print()}除了输出‘’号以外没有意义那么后缀表达式 产生式可能是expr → expr term 这个用于描述后缀表达式这也是参考答案的写法但是AI不同意强烈不建议这样写在AI的理解这个语句“expr → expr term ”不能被解析器正确解析其余理由我贴到了答案后面因此目前还是按照中缀表达式书写的答案虽然AI也不建议这样写他认为没有什么作用在真正的编译器设计中print操作通常不会出现在文法产生式中一个更实际的解决方案可能是编写一个解析器...问题2 除此以外我的解法语法可能有问题没有区分优先等级且会非常随意地加很多括号给表达式话说这如果是算法题答成这样一半分就没有了...答题后贴的参考答案避免了这个问题答案链接已贴于文首价值相对高一些~~ 思路 后缀表达式没有括号按从左到右的顺序运算运算符的优先级别是相等的如果我没有记错的话而转换为的中缀表达式可能有括号。例如执行4 5 6 * 读到 4压入栈。读到 5压入栈。读到 6压入栈。此时栈中有三个操作数4、5 和 6。读到 弹出 5 和 6形成中缀子表达式 5 6并将其作为一个整体结果可能带有括号暂存或输出。此时栈中应该只剩下 4。读到 *弹出 4 和刚才得到的中缀子表达式 5 6。形成最终的中缀表达式 4 * (5 6)。 答题 产生式 expr → expr { operator term }
term → digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
operator → | - | * | / 语义规则 expr → {print(()} expr { operator{print(operator)} term } {print())}
term → digit | print(digit);
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
operator → | - | * | / AI审核
1我曾问过AI它将后缀表达式的第一行写为expr → term { operator term }而非更符合后缀表达式形式的expr → term { term operator}呢 在后缀表达式也称为逆波兰表示法中操作数项即term位于操作符之前。因此当我们将后缀表达式转换为其他形式如中缀表达式时我们需要确保操作数的顺序正确。例如在后缀表达式“3 4 ”中加法操作符“”位于操作数“3”和“4”之后。因此在转换为中缀表达式时我们需要将操作数重新排序为“3 4”这正是“expr → term { operator term }”产生式所反映的结构。在文法定义中“expr → term { operator term }”这样的产生式意味着表达式expr由一个项term开始后面可能跟着一个或多个由操作符operator和另一个项term组成的序列。在后缀表达式中操作符总是位于它操作的两个操作数之后。如果我们写成“expr → term { term operator }”这实际上是不正确的因为它暗示了操作符后面紧跟着的是另一个项然后才是之前的项这与后缀表达式的实际结构相反。简单来说这个产生式错误地指示了解析器先去寻找一个项term然后去寻找另一个项最后才去寻找操作符operator。这实际上与后缀表达式的结构不符因为在后缀表达式中操作符应该紧跟在它的操作数之后。。简而言之正确的顺序“term operator term”反映了在后缀表达式中操作符位于两个操作数之后的事实而错误的顺序“term term operator”则不符合这种结构。 参考答案
productions:
expr - expr expr | expr expr -| expr expr *| expr expr /| digit translation schemes:
expr - expr {print()} expr | expr {print(-)} expr -| {print(()} expr {print()*()} expr {print())} *| {print(()} expr {print()/()} expr {print())} /| digit {print(digit)} Another reference answer
E - {print(()} E {print(op)} E {print()}} op | digit {print(digit)}
练习2.3.3
题目 构建一个将整数翻译成罗马数字的语法制导方案。 思路 罗马数字的组合规则可以总结如下 基本符号罗马数字系统使用七个不同的符号来表示数值I (1)、V (5)、X (10)、L (50)、C (100)、D (500) 和 M (1000)。 数值表示 I、X、C 和 M 可以被重复最多三次来表示它们的倍数例如II 2, XXX 30, CC 200, 但 IIII 不是标准的表示法应为 IV。V、L 和 D 不可以被重复。 减法原则当一个小数值的符号出现在一个较大数值的符号左边时表示应从大数中减去小数例如IV 4, IX 9, XL 40, XC 90, CD 400, CM 900。 加法原则当一个小数值的符号出现在一个较大数值的符号右边时或者相同数值的符号连续出现时表示应将它们相加例如VI 6, XI 11, XX 20, CCC 300。 避免重复四次罗马数字中不会出现连续四个相同的符号如 IIII 或 XXXX。应使用减法原则来表示这些数值如 IV 代替 IIIIXL 代替 XXXX。 从左到右罗马数字应从左到右按照上述规则进行解读。 千位以上的表示千位以上的数字可以通过重复 M 来表示例如MM 2000, MMM 3000。 组合顺序在表示一个数时应从最高位开始逐步降低到最低位。例如数字 1994 应表示为 MCMXCIV1000 (1000 - 100) (100 - 10) (5 - 1)。 零的表示罗马数字系统中没有专门的符号来表示零。零值是通过省略相应的符号来表示的。 基于以上规则一个更准确且简化的罗马数字文法可能是这样的请注意这个文法仍然不是完美的因为它允许像 IIII 这样的非标准表示 roman → thousand* hundred ten unit
thousand → M {M}
hundred → CM | CD | C {C | CC | CCC} | D {C | CC | CCC} | M {CM | CD | C {C | CC | CCC} | D {C | CC | CCC}}
ten → XC | XL | X {X | XX | XXX} | L {X | XX | XXX} | IX | IV | V {I | II | III} | I {X | V}
unit → I {I | II | III} | IV | V {I | II | III} | VI | VII | VIII | IX 答题
经过前3道题与AI无尽的争吵具体来说我对于语法学不明白而AI觉得语法制导翻译方案不实用因此我们决定彻底摆烂以下用C代码解题
#include string
#include iostream
using namespace std;std::string intToRoman(int num) {std::string roman ;std::string thousands[] { , M, MM, MMM };std::string hundreds[] { , C, CC, CCC, CD, D, DC, DCC, DCCC, CM };std::string tens[] { , X, XX, XXX, XL, L, LX, LXX, LXXX, XC };std::string ones[] { , I, II, III, IV, V, VI, VII, VIII, IX };// 千位 roman thousands[num / 1000];num % 1000;// 百位 roman hundreds[num / 100];num % 100;// 十位 roman tens[num / 10];num % 10;// 个位 roman ones[num];return roman;
}int main() {int number 0;cout 请输入整数0-3999\t ;cin number;string romanNumeral intToRoman(number);cout romanNumeral std::endl;return 0;
} 练习2.3.4
题目 构建一个将罗马数字翻译成整数的语法制导方案。 答题
#include iostream
#include string
#include unordered_map int romanToInt(std::string s) {std::unordered_mapchar, int romanValues {{I, 1},{V, 5},{X, 10},{L, 50},{C, 100},{D, 500},{M, 1000}};int result 0;// 从左向右遍历字符串取出第i个字符for (size_t i 0; i s.length(); i) {int value romanValues[s[i]];// 若第i1个字符存在且第i个字符第i1个字符则结果减去第i个字符的值第3条减法原则反之则增加第i个字符的值第4条加法原则if (i 1 s.length() value romanValues[s[i 1]]) {result - value;}else {result value;}}return result;
}int main() {std::string romanNumeral MMMDXLIX;int number romanToInt(romanNumeral);std::cout number std::endl; // 输出: 3549 return 0;
} 结语
博文到此结束写得模糊或者有误之处欢迎小伙伴留言讨论与批评督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等博主会顶锅前来修改~~️️
我是梅头脑本片博文若有帮助欢迎小伙伴动动可爱的小手默默给个赞支持一下感谢点赞小伙伴对于博主的支持~~
同系列的博文编译原理_梅头脑_的博客-CSDN博客
同博主的博文随笔03 笔记整理-CSDN博客
