编译原理2.3习题语法制导分析[C++]

编译原理2.3习题语法制导分析[C++]-LMLPHP

图源：文心一言

编译原理习题整理~🥝🥝

作为初学者的我，这些习题主要用于自我巩固。由于是自学，答案难免有误，非常欢迎各位小伙伴指正与讨论！👏💡

第1版：自己的解题，与AI老师的判卷~🧩🧩

编辑：梅头脑🌸

审核：文心一言

题源：龙书《编译原理》 Alfre V.Aho 等著赵建华等译

🧵参考答案

🧵练习2.3.1

🧩题目

📇答题

📇AI审核

1：我曾问过AI，它习惯将第一行写为expr → term { ("+" | "-") term }，这实际与教材中书写的expr → expr { ("+" | "-") term }不同，为什么不写为后者呢？

📇知识扩展

🧵练习2.3.2

🧩题目

📇争议

📇思路

📇答题

📇AI审核

1：我曾问过AI，它将后缀表达式的第一行写为expr → term { operator term }，而非更符合后缀表达式形式的expr → 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

🧩题目

📇思路

📇答题

经过前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_map<char, 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]];
        // 若第i+1个字符存在，且第i个字符<第i+1个字符，则结果减去第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博客

梅头脑_