编译原理2.2习题语法定义

?1）生成过程?????
S   → SS* (应用第2个产生式：S → SS*)  
    → SS+a* (第1个S应用第1个产生式：S → SS+，第2个S应用第3个产生式：S → a,*保留)  
    → aa+a* (第1、第2个S都应用第3个产生式：S → a)
2）语法分析树

3）~~包含了 + 、* 与 a 的字符串，且字符串以a开头。?~~

📇AI审核

AI回复详细版本：

Ps：话说，我和AI在这道题目上吵起来了，过程按下不表（AI逻辑自我矛盾，还贼犟），导致我很生气地看了两个小时的电视剧冷静了一下💢，回来又开了一个新话题更加细致地讲了一遍，他终于给到了很好的答案（就是如下），瘫；话说，小伙伴们有和AI吵架的经验嘛？

对于您提供的答案，我将分别进行审核：
1）生成过程：
第二步中存在一个问题：原始文法没有直接提供将S*转换为S+*或a*的产生式。这里似乎进行了一个不规范的步骤，即将S*解释为S的后缀并保留*。严格来说，这样的步骤需要更明确的解释或修改文法以允许这样的推导。
一个更严格的推导可能需要引入额外的步骤或使用不同的策略，因为按照给定的文法，S*不能直接被解释为a*。
2）语法分析树：
尽管我选择了与图有关的所有插件，但他好像还是看不到我画的图，因为暂时没办法一边发图一边发文字，不过他自己能用代码画一个我还是很震惊的（虽然，他应该是没画对）。
S  
├── S → a  
│   └── (终结符)  
├── S → a  
│   └── (终结符)  
├── +   (终结符)  
└── S*  (这里有问题，因为*是终结符，而S*不是文法中的一个非终结符)  
    └── S → a  
        └── (终结符)
3）该文法生成的语言：
您的回答指出生成的语言是“包含了 + 、* 与 a 的字符串，且字符串以a开头”。这个描述是不准确的，因为给定的文法可以生成比这更复杂的字符串。
实际上，给定的文法：S → SS+|SS*|a?是一个有问题的文法，因为它同时使用了+和*作为终结符，这在传统的上下文无关文法中是不常见的。如果+和*被当作元符号（表示一个或多个以及零个或多个），那么这个文法就是二义性的，因为它没有正确地定义这些元符号的优先级和结合性。
如果+和*确实是终结符，并且文法是正确的（尽管这在实际中很少见），那么生成的语言将包括所有可以通过该文法的产生式生成的字符串。这些字符串将包含a、+和*，但它们的形式将受到产生式结构的限制，而不仅仅是“以a开头”。
一个更准确的描述可能是：“该文法生成的语言是所有可以通过重复应用产生式S → SS+、S → SS*或S → a得到的后缀表达式，其中这些表达式包含终结符a、+和* ”但请注意，由于文法的定义方式，实际上很难给出一个既准确又简洁的描述，除非我们对文法有更深入的了解或文法被修改以澄清这些符号的作用。

AI回复简单版本：

生成过程问题：
原始文法?S → SS+|SS*|a?没有直接支持?S*?到?a*?的转换。
需要更明确的推导步骤或修改文法。
语法分析树问题（这条被我删掉，无法审图，因此建议无效）
文法生成的语言描述问题：
描述为“包含了?+、*?与?a?的字符串，且字符串以?a?开头”是不准确的。
更准确的描述应考虑所有通过文法产生式生成的字符串形式。

建议：

如果目标是生成后缀表达式，重新设计文法以正确处理运算符的优先级和结合性。
清晰定义?+?和?*?的角色（作为终结符还是元符号）。
在构造语法分析树时，确保遵循文法的产生式规则。

🧵练习2.2.2

🧩题目

下面的各个文法生成什么语言？证明你的每一个答案：

1）S → 0S1|01
2）S → +SS|-SS|a
3）S → S(S)S|ε
4）S →?aSbS|bSaS|ε
5）S →?a|S+S|SS|S*|(S)

📇阿梅答题

~~1）以‘0’开头的，‘0’、‘1’为元素的字符串；~~
~~2）以‘a’为元素，进行‘+’、'-'运算的前缀表达式；~~
~~3）以'S'与‘()’为元素的字符串；~~
~~4）以'a'、'b'或空集为元素的字符串；~~
~~5）以‘a’或'aa'为元素，进行‘+’、'*'、'()'运算的中缀表达式；~~

📇AI审核

对于文法 1）S → 0S1|01
提供的答案：“以‘0’开头的，‘0’、‘1’为元素的字符串”是不准确的。
正确的语言描述：这个文法生成的是所有以‘0’开头，以‘1’结尾，并且‘0’和‘1’交替出现的字符串，且至少包含一个‘0’和一个‘1’。
证明：通过归纳法可以证明。基础情况是字符串“01”。归纳步骤是，如果字符串w是形式为“0...1”的字符串，那么“0w1”也是一个这样的字符串。
对于文法 2）S → +SS|-SS|a
提供的答案：“以‘a’为元素，进行‘+’、'-'运算的前缀表达式”是不完全准确的。
正确的语言描述：这个文法生成的是所有由单个‘a’或者通过‘+’和‘-’运算符连接的两个S表达式组成的前缀表达式。
证明：这个文法的前两个产生式生成了运算符在前、操作数在后的标准前缀表达式形式。基础情况是‘a’，归纳步骤是通过‘+’或‘-’将两个较小的前缀表达式组合成一个较大的前缀表达式。
对于文法 3）S → S(S)S | ε
提供的答案：“以'S'与‘()’为元素的字符串”是不准确的
正确的语言描述应该是：这个文法生成的是所有正确匹配的括号序列，其中括号可以嵌套，并且序列可以为空（由于ε的存在）。这里的‘S’并不是生成的字符串的一个元素，而是文法的一个非终结符，它代表可以进一步展开的子串。

证明：

基础情况：空串ε是该文法生成的一个字符串，因为文法中有一个产生式直接生成ε。
归纳步骤：如果w是由该文法生成的一个字符串，那么“(w)”也是由该文法生成的一个字符串，这是通过应用产生式S → S(S)S并令其中的两个S生成ε而得到的。类似地，如果w1、w2和w3都是由该文法生成的字符串，那么“w1(w2)w3”也是由该文法生成的一个字符串，这是通过多次应用产生式S → S(S)S或S → ε而得到的。
注意，由于这个文法允许括号嵌套，因此它可以生成任意深度嵌套的正确匹配的括号序列。同时，由于ε的存在，它也可以生成不包含任何括号的空串。但是，它不会生成包含不匹配的括号或单个括号的字符串。
对于文法 4）S →?aSbS|bSaS|ε
提供的答案：“以'a'、'b'或空集为元素的字符串”是不准确的。
正确的语言描述：这个文法生成的是所有具有相等数量的‘a’和‘b’，并且每个‘a’后面都跟着一个‘b’，以及每个‘b’前面都有一个‘a’的字符串，包括空串。
证明：基础情况是空串ε。归纳步骤是，如果字符串w是满足条件的字符串，那么“aWb”和“bWa”（其中W是w的某种排列）也是满足条件的字符串。但这里有个问题，因为给出的文法并不能直接生成“bWa”形式的字符串，所以文法可能是有误的，或者答案需要更精确地描述为只能生成“a...b...a...b...”形式的字符串。
对于文法 5）S →?a|S+S|SS|S*|(S)
提供的答案：“以‘a’或'aa'为元素，进行‘+’、'*'、'()'运算的中缀表达式”是不准确的。
正确的语言描述：这个文法生成的是所有由单个‘a’、通过‘+’、‘*’和括号进行组合的标准中缀表达式。
证明：基础情况是‘a’。归纳步骤是通过‘+’、‘*’和括号将较小的中缀表达式组合成较大的中缀表达式。注意，这个文法允许嵌套括号和运算符的任意组合，只要它们符合标准的中缀表达式形式。

📇参考答案

L = {0^n1^n | n>=1}
L = {Prefix expression consisting of plus and minus signs}
L = {Matched brackets of arbitrary arrangement and nesting, includes ε}
L = {String has the same amount of a and b, includes ε}
L = {Regular expressions used to describe regular languages}

http://en.wikipedia.org/wiki/Regular_expression

L =｛0^n1^n | n>=1｝

L =｛由加号和减号组成的前缀表达式｝

L =｛任意排列和嵌套的匹配括号，包括ε｝

L =｛字符串具有相同数量的a和b，包括ε｝

L =｛用于描述正则语言的正则表达式｝

🧵练习2.2.3

🧩题目

练习2.2.2中哪些文法具有二义性？

📇阿梅答题

1）不具有二义性；

2）不具有二义性，但如果增加ε，则可能导致二义性；

3）具有二义性；

4）具有二义性；

5）具有二义性；

🧵练习2.2.4

🧩题目

为下面的各个语言构建无二义性的上下文无关文法，证明你的文法都是正确的。

1）用后缀方式表示的算术表达式；
2）由逗号分隔开的左结合标识符列表；
3）由逗号分隔开的右结合标识符列表；
4）由整数、标识符、四个二目运算符+、-、*、/构成的算数表达式；
！5）在4）的运算符中增加单目+ 和单目- 构成的算数表达式。

📇阿梅答题

1）~~list?→ list digit opt | digit?????~~???
2）list?→ list , id | id
3）list?→ id , list | id
4）
~~expr → expr + term | expr - term | term~~
~~term → term * factor | term / factor | factor~~
~~factor?→ int | id | (expr)?~~
5）
~~expr → expr + term | expr - term | expr + | expr - | term~~
~~term → term * factor | term / factor | term * | term / | factor~~
~~factor?→ int | id | (expr)?~~

📇AI审核

1.为后缀方式表示的算术表达式构建无二义性的上下文无关文法

您的答案似乎没有正确地为后缀算术表达式构建文法。后缀表达式中，运算符位于其操作数之后，例如“3 4 +”。此外，您的答案中使用了“digit”而不是涵盖更广泛情况的“expr”或类似的非终结符。

一个正确的无二义性文法来解析后缀表达式可能如下所示：
expr → value | expr value operator  
value → int | identifier  
operator → "+" | "-" | "*" | "/"  
int → "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | int int  
identifier → letter { letter | digit }  
letter → "a" | "b" | "c" | ... | "z" | "A" | "B" | "C" | ... | "Z"  
digit → "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
但是，这个文法仍然有些问题。

首先，它允许?int?非终结符递归地引用自身，这在实际的词法分析中通常不是必需的，因为整数通常是由词法分析器一次性识别的。

其次，expr?的产生式没有正确地表示后缀表达式的结构，因为它试图将运算符放在两个值之间，而不是之后。

实际上，对于后缀表达式，我们可能需要一个稍微不同的处理方法。由于后缀表达式的结构，我们通常不会使用递归下降解析器来处理它们，而是使用一个栈。不过，如果我们仍然想要一个上下文无关文法来表示它们，我们可以尝试以下方法：
postfix → value { operator value }  
value → int | identifier  
operator → "+" | "-" | "*" | "/"  
int → nonzero-digit { digit }  
nonzero-digit → "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"  
                // 注意："0" 不应该单独作为一个 int 的开头，除非它是唯一的数字  
identifier → letter { letter | digit }

2.由逗号分隔开的左结合标识符列表

您的答案：list → list , id | id?是正确的。这确实表示了由逗号分隔的左结合标识符列表。

3.由逗号分隔开的右结合标识符列表

您的答案：list → id , list | id?是不完全正确的。这个文法会产生右递归，但它实际上表示的仍然是一个左结合的列表，因为最右边的标识符会最先被解析。真正的右结合是非常罕见的，并且在这种上下文中可能没有实际意义。

不过，如果您的意图是生成一个从右到左解析的列表（尽管这不符合通常的“右结合”定义），那么这个文法是可以的。

4.由整数、标识符、四个二目运算符+、-、*、/构成的算数表达式

这个文法正确处理了运算符的优先级，但没有处理结合性（它假设了左结合）。

正确答案：

expr → term { ("+" | "-") term }  
term → factor { ("*" | "/") factor }  
factor → integer | identifier | "(" expr ")"  
integer → digit { digit }  
identifier → letter { letter | digit }  
digit → "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"  
letter → "a" | "b" | "c" | ... | "z" | "A" | "B" | "C" | ... | "Z"

5.在4）的运算符中增加单目+和单目-构成的算数表达式

您的答案尝试在原有文法上增加单目运算符，但这样做的方式是不正确的。单目运算符应该应用于因子级别，而不是表达式或项级别。一个可能的正确文法如下：
expr → term { ("+" | "-") term }  
term → factor { ("*" | "/") factor }  
factor → ("+" | "-") factor | integer | identifier | "(" expr ")"  
integer → digit { digit }  
identifier → letter { letter | digit }  
digit → "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"  
letter → "a" | "b" | "c" | ... | "z" | "A" | "B" | "C" | ... | "Z"
在这个修改后的文法中，factor?可以是一个单目运算符后跟另一个?factor，也可以是一个整数、标识符或括号内的表达式。这样，我们就可以处理像?-x、+y?这样的单目运算符表达式了。

请注意，这里的文法假设了运算符的优先级和结合性，并且没有显式地处理空格、制表符或其他可能的空白字符。在实际应用中，这些通常是由词法分析器处理的。

🧵练习2.2.5

🧩题目

1）证明：用下面文法生成的所有二进制串的值都能被3整除。（提示：对语法分析树的结点数目使用数学归纳法。）

num→ 11 | 1001 | num0 | num num

2）上面的文法是否能生成所有能被3整除的二进制串？

📇阿梅答题

?回想起了被log3支配的恐惧：🌸C++代码入门01 幂运算与对数运算-CSDN博客

1）毫无章法的证明如下：

11 二进制是 3，可以被3整除；
110 二进制是 6，可以被3整除；11+n个0，二进制是3*（2^n），可以被3整除；
1001 二进制是9，可以被3整除；
10010 二进制是18，可以被3整除；1001+m个0，二进制是 9* (2^m)，可以被3整除；
1111二进制是15，可以被3整除；11+n个11，大概也是能被3整除的（因为可以写作1100+11这样的，而前者、后者都是3的倍数）；
同理，m个11 + n个1001任意组合，即a * 3*（2^n）+ b * 9* (2^m) 也是能被3整除的；

2）让我想想，如果用枚举法：3（11），6（11+0），9（1001），12（11+00），15（11+11），18（1001+0），21（10101，哎等等，这个怎么生成？）

📇AI审核

1.证明用文法生成的所有二进制串的值都能被3整除

基础步骤：

证明基础情况。根据文法，最基础的情况是由产生式?num → 11 | 1001?直接生成的字符串。这些字符串分别代表十进制数3和9，都是3的倍数。

归纳假设：

假设对于所有由k次或更少次应用文法的产生式得到的字符串，它们所代表的数都能被3整除。这里的k是一个非负整数。

归纳步骤：

证明如果对于所有由k次或更少次应用产生式得到的字符串，它们所代表的数都能被3整除，那么对于由k+1次应用产生式得到的字符串也成立。

对于形式为?num0?的字符串，它是由k次或更少次应用产生式得到的字符串后面添加了一个0。在二进制中，末尾添加一个0相当于将数乘以2。由于乘以2不会改变一个数是否能被3整除的性质，因此如果原始字符串代表的数能被3整除，那么添加0后的字符串代表的数也能被3整除。

对于形式为?num num?的字符串，它是由两个由k次或更少次应用产生式得到的字符串拼接而成。如果两个字符串分别代表的数都能被3整除，那么它们的和也能被3整除。在二进制中，拼接两个字符串相当于将它们代表的数相加（考虑到适当的位移）。因此，如果两个原始字符串代表的数都能被3整除，那么拼接后的字符串代表的数也能被3整除。

通过基础步骤和归纳步骤，我们可以得出结论：由给定文法生成的所有二进制串所代表的数都能被3整除。

但是，请注意，上述解释中有一些不严谨的地方，特别是在处理“大概也是能被3整除的”这样的表述时。一个更严谨的证明会避免这样的模糊性，并严格遵循数学归纳法的结构。

2.文法是否能生成所有能被3整除的二进制串？

这个问题比较复杂。我们已经证明了文法生成的所有二进制串都能被3整除，但反过来并不成立：不是所有能被3整除的二进制串都能由这个文法生成。

例如，10101（二进制）对应于十进制中的21，能被3整除，但它不能由给定的文法生成。这个文法无法生成包含单个1的二进制串，因此像10101这样的串就无法生成。

所以，这个文法不能生成所有能被3整除的二进制串。

📇参考答案

从语法派生的任何字符串都可以被认为是一个由 11 和 1001 组成的序列，其中每个序列元素都可能以 0 为后缀。

设 n 是放置 11 的位置集。如果 11 中的前 1 位于位置 I，则称 11 位于位置 I，其中 i 从 0 开始并且从最低有效位增长到最高有效位。

设 m 是 1001 的等效集。

语法生成的任何字符串的总和为：

sum

= Σn （2^1 + 2^0） * 2^n + Σm （2^3 + 2^0） * 2^m

= Σn 3 * 2^n + Σm 9 * 2^m

这显然可以被 3 整除。

🧵练习2.2.6

🧩题目

为罗马数字构建一个上下文无关文法。

📇阿梅答题

?我决定抄袭AI的答案改一改，它的答案已经写得很好了~~

expr → term { ("+" | "-") term }  
term → factor { ("*" | "/") factor }  
factor → ("+" | "-") factor | integer |  "(" expr ")"  
integer → digit { digit }  
digit → "N" | "Ⅰ" | "Ⅱ" | "Ⅲ" | "Ⅳ" | "Ⅴ" | "Ⅵ" | "Ⅶ" | "Ⅷ" | "Ⅸ" | "L" | "C" | "D" | "M" |

但还是被AI批评了一顿——

📇AI审核

您给出的上下文无关文法看起来更像是为四则运算表达式设计的，而不是专为罗马数字构建的。此外，您在digit规则中使用了一些不正确的罗马数字符号（比如“N”和“L”作为单个符号，实际上在罗马数字中它们通常与其他符号组合使用，如“XL”或“LV”等），并且还包括了一些不正确的字符（如结尾的中文字符“”）。

要为罗马数字构建一个上下文无关文法，我们需要考虑罗马数字的基本规则和组合方式。罗马数字主要由以下符号构成：I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。这些符号可以组合成更大的数字，但需要遵循一定的规则，如较小的数字在较大的数字左边表示减法，而在右边表示加法。

以下是一个简化的上下文无关文法，用于生成罗马数字：
roman → thousand { thousand } | hundred { hundred } | ten { ten } | one { one }  
thousand → "M" | "CM" | "CD" | "DCCC" | "CMCCC" | ... (其他表示1000以上数字的合法组合)  
hundred → "C" | "CC" | "CCC" | "CD" | "D" | "DC" | "DCC" | "CMC" | ... (其他表示100以上数字的合法组合)  
ten → "X" | "XX" | "XXX" | "XL" | "L" | "LX" | "LXX" | "XC" | ... (其他表示10以上数字的合法组合)  
one → "I" | "II" | "III" | "IV" | "V" | "VI" | "VII" | "VIII" | "IX" | ... (其他表示1以上数字的合法组合)
然而，上面的文法并不是最简化的形式，因为它包含了大量的重复和可能的组合。实际上，我们可以进一步简化文法，考虑到罗马数字的规则和限制。以下是一个更加简化和精确的上下文无关文法：
roman → millenium { millenium } | roman_rest  
millenium → "M"  
roman_rest → century roman_rest | decade roman_rest | unit roman_rest | ε  
century → "CM" | "CD" | "C" century_rep | "D" century_rep | "DC" century_rep  
century_rep → "C" | "CC" | "CCC"  
decade → "XC" | "XL" | "X" decade_rep | "L" decade_rep | "LX" decade_rep  
decade_rep → "X" | "XX" | "XXX" | "XL" | "L"  
unit → "IX" | "IV" | "I" unit_rep | "V" unit_rep | "VI" unit_rep | "VII" | "VIII"  
unit_rep → "I" | "II" | "III"  
ε → (空字符串，表示文法的结束)
请注意，上面的文法仍然不是最完整的，因为罗马数字的实际使用中有更多的规则和特例（比如“CM”只能出现在“D”之前，而“CD”只能出现在“C”之前等）。构建一个完整且精确的罗马数字文法可能需要更多的工作和详细的规则。但是，这个简化的版本应该能够给您一个大致的方向。

📇参考答案

wikipedia: Roman_numerals
via wikipedia, we can categorize the single roman numerals into 4 groups:
I, II, III | I V | V, V I, V II, V III | I X
then get the production:
digit -> smallDigit | I V | V smallDigit | I X
smallDigit -> I | II | III | ε
and we can find a simple way to map roman to arabic numerals. For example:

XII => X, II => 10 + 2 => 12
CXCIX => C, XC, IX => 100 + 90 + 9 => 199
MDCCCLXXX => M, DCCC, LXXX => 1000 + 800 + 80 => 1880

via the upper two rules, we can derive the production:

romanNum -> thousand hundred ten digit

thousand -> M | MM | MMM | ε

hundred -> smallHundred | C D | D smallHundred | C M

smallHundred -> C | CC | CCC | ε

ten -> smallTen | X L | L smallTen | X C

smallTen -> X | XX | XXX | ε

digit -> smallDigit | I V | V smallDigit | I X

smallDigit -> I | II | III | ε

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~~😶?🌫?😶?🌫?

我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，感谢点赞小伙伴对于博主的支持~~🌟🌟

同系列的博文：🌸编译原理_梅头脑_的博客-CSDN博客

同博主的博文：🌸随笔03 笔记整理-CSDN博客

文章来源:https://blog.csdn.net/weixin_42789937/article/details/135679323
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

编译原理2.2习题 语法定义

🧵参考答案

🧵练习2.2.1

🧵练习2.2.2

🧵练习2.2.3

🧵练习2.2.4

🧵练习2.2.5

🧵练习2.2.6

🔚结语

编译原理2.2习题语法定义