编译原理2

1. (编译原理) 求下述文法对应正规式： S->0A|1B A->1S|1 B->0S|0

一、简单的推导思路
1、该文法的对应正规式为：[01|10]+
2、推导：
（1）首先，展开产生式S，可知S要么以0开头，要么以1开头；
（2）如果S按产生式S->0A展开，则S必以01开头，因为通过产生式A->1S|1可知，A必定是以1开头的；
（3）如果S按产生式S->1B展开，则S必以10开头，因为产生式B必定以0开头；
（4）综上，可知，S是以01或10开头的非终结符号；
（5）当A以产生式A->1展开或 B以B->0展开时，S将推导结束；
（6）当A以产生式A->1S展开或 B以B->0S展开时，产生式中的非终结符号S将重复（1）-（3）的推导步骤；
（7）综上所述，该文法的对应正规式为：[01|10]+。

二、联立方程组求解
假设非终结符号S、A、B都分别代表一个正规式，则正规文法的产生式集合所代表的就是关于正规式S、A、B的一个方程组。
我们将文法“|”符号替换为正规式“+”符号，可得，
S=0A+1B=0(1S+1)+1(0S+0)=01(S+ε)+10(S+ε)=(01+10)(S+ε)=(01+10)S+(01+10)。
根据方程X=rX+t有形如X=r*t的解论断，可得，
S=(01+10)*(01+10)=[01|10]+。

2. 编译原理中，形式语言里怎么区分2型文法与3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法 。
B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端 。
D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：
1）空串
2）只有一个终结符
3）只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。

3. 【编译原理】第二章：语言和文法

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：

产生式

可以简写为：

如上例中，

可以简写为：

给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。

如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。

推导的反过程称为 归约 。

如果 ，则称 是 的一个 句型（sentential form ）。

由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：

例
文法

表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。
如上例表示为：

中必须包含一个 非终结符 。

产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。

上下文有关文法不包含空产生式（ ）。

产生式的一般形式：
即产生式左边都是非终结符。

右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：

正则文法能描述程序设计语言中的多数单词。

正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。

根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。

直接短语一定是某产生式的右部，但反之不一定。

如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。

二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。

4. 璁＄畻链虹戝︿笡涔β风紪璇戝师鐞嗗唴瀹圭亩浠

璁＄畻链虹戝﹂嗗烟链変竴链澶囧弹鎺ㄥ磭镄勮宪浣溾斺斻婄紪璇戝师鐞(链绉戞暀瀛︾増绗2鐗)銆嬨傝繖链涔︾粡杩囩簿蹇冩敼缂栵纴鐩歌缉浜庣涓鐗堬纴鍐呭规洿锷犵簿镣间笖瀹炵敤镐ф洿寮猴纴瀹冩洿锷犺创钖堟垜锲介珮镙¤＄畻链轰笓涓氱殑鏁椤﹂渶姹伞备綔涓烘湰绉戠敓缂栬疟铡熺悊璇剧▼镄勭悊𨱍虫暀𨱒愶纴镞犺烘槸瀵逛笓涓氩︾敓杩樻槸镰旂┒浜哄憳锛岄兘鍏锋湁鏋侀珮镄勫弬钥冧环鍊笺

琚瑾変负钬滈緳涔︹濈殑銆婄紪璇戝师鐞(链绉戞暀瀛︾増绗2鐗)銆嬭嚜1986骞撮梾涓栦互𨱒ワ纴涓鐩村弹鍒板叏鐞幂煡钖嶅﹀簻镄勯潚镌愶纴濡傚掼浼︽瘆浜氩ぇ瀛︺佹柉鍧︾忓ぇ瀛︺佸搱浣涘ぇ瀛﹀拰鏅鏋楁柉椤垮ぇ瀛︾瓑锛屽畠浠閮藉皢姝や功浣滀负缂栬疟铡熺悊璇剧▼镄勯栭夋暀𨱒愩傚湪涓锲斤纴璇ヤ功瀵归珮绛夋暀镶查嗗烟灏ゅ叾浜х敓浜嗘繁杩滃奖鍝嶏纴鎺ㄥ姩浜嗙紪璇戞妧链镄勬暀瀛﹀拰镰旂┒銆

鍦ㄧ浜岀増涓锛屼綔钥呭瑰悇绔犺妭杩涜屼简鍏ㄩ溃镄勬洿鏂帮纴浠ュ弽鏄犺繃铡20澶氩勾杞浠跺伐绋嬨佺▼搴忚捐¤瑷鍜岃＄畻链轰綋绯荤粨鏋勯嗗烟镄勮繘姝ワ纴濡备綍褰卞搷浜嗙紪璇戞妧链銆傛柊鐗堟繁鍏ヨ茶В浜嗙紪璇戝櫒镄勮捐★纴骞剁潃閲嶅𪾢绀轰简缂栬疟鎶链鍦ㄨ蒋浠跺紑鍙戜腑镄勫箍娉涘簲鐢ㄣ傛疮涓绔犺妭閮介厤浠ヤ赴瀵岀殑涔犻桡纴鏂逛究瀛︾敓杩涜屽疄璺电粌涔狅纴钖屾椂鎻愪緵浜嗗厖瓒崇殑鍙傝冩枃鐚渚涜繘涓姝ュ︿範銆

阍埚瑰浗鍐呯殑鏁椤﹂渶姹傦纴鏂扮増銆婄紪璇戝师鐞(链绉戞暀瀛︾増绗2鐗)銆嫔垹鍑忎简閮ㄥ垎楂樼骇鍐呭癸纴淇濈暀浜嗗熀纭鐭ヨ瘑锛屾棬鍦ㄦ彁渚涗竴涓镟翠负阃傚悎璁＄畻链哄强鐩稿叧涓扑笟链绉戠敓瀛︿範镄勬暀𨱒愶纴甯锷╀粬浠寤虹珛璧峰潥瀹炵殑缂栬疟铡熺悊锘虹銆

5. 编译原理 2型文法一定是1型文法吗 不是一种包含关系吗

2型文法一定是1型文法吗？--是的，一定是，3型文法一定是2型的，2型一定是1型的，1型一定是0型的。
只不过考试时候需要最准确的回答，如果考试问一个文法G1（是2型的），你回答0型，1型，2型都没错，但是回答2型才是最准确的，单选也是，需要回答2型，复选题的话你就得选 0型、1型、2型了。