Ⅰ 编译原理笔记9：语法分析树、语法树、二义性的消除
语法分析树和语法树不是一种东西 。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。
语法分析树是语言推导过程的图形化表示方法。这种表示方法反映了语言的实质以及语言的推导过程。
定义：对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：
推导，有最左推导和最右推导，这两种推导方式在推导过程中的分析树可能不同，但因最终得到的句子是相同的，所以最终的分析树是一样的。
分析树能反映句型的推导过程，也能反映句型的结构。然而实际上，我们往往不关心推导的过程，而只关心推导的结果。因此，我们要对 分析树 进行改造，得到 语法树 。语法树中全是终结符，没有非终结符。而且语法树中没有括号
定义：
说白了，语法树这玩意，就一句话： 叶子全是操作数，内部全是操作符 ，树里没有非终结符也不能有括号。
语法树要表达的东西，是操作符（运算）作用于操作数（运算对象）
举俩例子吧：
【例】： -(id+id) 的语法树：
【例】：-id+id 的语法树：
显然，我们从上面这两个语法树中，直接就能观察出来它们的运算顺序。
【例】：句型 if C then s1 else s2
二义性问题：一个句子可能对应多于一棵语法树。
【例】： 设文法 G： E → E+E | E*E | (E) | -E | id
则，句子 id+id*id、id+id+id 可能的分析树有：
在该例中，虽然 id+id+id 的 “+” 的结合性无论左右都不会影响结果。但万一，万一“+”的含义变成了“减法”，那么左结合和右结合就会引起很大的问题了。
我们在这里讲的“二义性”的“义”并非语义——我们现在在学习的内容是“语法分析器”，尚未到需要研究语言背后含义的阶段。
我们现在讲的“二义性”指的是一个句子对应多种分析树。
二义性的体现，是文法对同一句子有不止一棵分析树。这种问题由【句子产生过程中的某些推导有多于一种选择】引起。悬空 else 问题就可以很好地体现这种【超过一种选择】带来的二义性问题，示例如下。
看下面这么个例子。。
（其实，我感觉这个其实比较像是“说话大喘气”带来的理解歧义问题。。。）上面的产生式中并没体现出来该咋算分一块，所以两种完全不同的句子结构都是合法的。
二义性问题是有救的，大概有以下这三种办法：
这些办法的核心，其实都是将优先级和结合性说明白。
核心：把优先级和结合性说明白
既然要说明白，那就不能让一个非终结符可以直接在当次推导中能推出会带来优先级和结合性歧义的东西。（对分析树的一个内部节点，不会有出现在其下面的分支是相同的非终结符的情况。如果有得选，那就有得歧义了。没得选才能确定地一路走到黑）
改写为非二义文法的二义文法大概有下面这几个特点：
改写的关键步骤：
【例】改写下面的二义文法为非二义文法。图右侧是要达成的优先级和结合性
改写的核心其实就两句话：
所以能够得到非终结符与运算的对应关系（因为不同的运算有不同的优先级，我们想要引入多个优先级就要引入多个新的非终结符。这样每个非终结符就可以负责一个优先级的运算符号，也就是说新的非终结符是与运算有关系的了。因此这里搞出来了“对应关系”四个字）如下：
优先级由低到高分别是 +、 、-，而距离开始符号越近，优先级越低。因此在这里的排序也可以+ -顺序。每个符号对应一层的非终结符。根据所需要的结合性，则可确定是左递归还是右递归，以确定新的产生式长什么样子
【例】：规定优先级和结合性，写出改写的非二义文法
我们已经掌握了一种叫做【改写】的工具，能让我们消除二义性。接下来我们就要用这个工具来尝试搞搞悬空 else 问题！
悬空 else 问题出现的原因是 then 数量多于 else，让 else 有多个可以结合的 then。在二义文法中，由于选哪两个 then、else 配对都可以，故会引起出现二义的情况。在这里，我们规定 else 右结合，即与左边最靠近的 then 结合。
为改写此文法，可以将 S 分为完全匹配（MS）和不完全匹配（UMS）两类。在 MS 中体现 then、else 个数相等即匹配且右结合；在UMS 中 then、else 不匹配，体现 else 右结合。
【例】：用改写后的文法写一个条件语句
经过检查，无法再根据文法写出其他分析树，故已经消除了二义性
虽然二义文法会导致二义性，但是其并非一无是处。其有两个显着的优点：
在 Yacc 中，我们可以直接指定优先级、结合性而无需自己重写文法。
left 表示左结合，right 表示右结合。越往下的算符优先级越高。
嗯就这么简单。。。
我们其实可以把语言本身定义成没有优先级和结合性的。。然后所有的优先、结合都交由括号进行控制，哪个先算就加括号。把一个过程的结束用明确的标志标记出来。
比如在 Ada 中：
在 Pascal 中，给表达式加括号：
Ⅱ 编译原理实验报告
#include<stdio.h>
void main()
{
int m=0,n=0,n1=0,n2=0,n3=0,zg,fzg,flag;
int bz[7]=;/*状态改变控制，1 表示可以改变状态zt值，0 表示不可以*/
int zt[7]=;/*状态值，2表示未定状态，1表示 是，0表示 否*/
char temp[100]="\0";/*用于求first集*/
char z[7];/*非总结符*/
char z1[7];/*总结符*/
char z2[7]="\0";/*gs[]文法中出现的标记个数的辅助字符 01234*/
char gs[100]="\0";/*文法，按顺序排成字符串*/
printf("请依次输入非终结符(不超过7个):");
gets(z);
while(z[m]!='\0')
fzg=m;//zg是非终结符个数
while(n<m)
//生成01234辅助字符
printf("您输入了:");
puts(z);
fflush(stdin);
printf("请依次输入终结符(不超过7个):");
gets(z1);
while(z1[n1]!='\0')
zg=n1;
printf("您输入了:");
puts(z1);
fflush(stdin);
printf("按照正确格式输入所有文法(总长度不超过100格式如下):");
printf("如果文法为(字符'k'表示空):\n");
printf("S-->AB S-->bC A-->k A-->b\n");
printf("输入:0SAB0SbC1Ak1Ab\n");
printf(" (注:数字01234表示第一二三四个非终结符)\n");
gets(gs);
fflush(stdin);
printf("您输入了:");
puts(gs);
m=0;
//对于输入文法字符串的转换，将每个文法式左部去除
while(gs[m]!='\0')
{
n=m;
if(gs[m]>='0'&&gs[m]<='9')
{
m++;
while(gs[m]!='\0')
{
gs[m]=gs[m+1];
m++;
}
//gs[m-1]='\0';
}
m=++n;
}
m=0;
//puts(gs);
/*情况一，直接判定是 形如: (A-->k) */
while(gs[m]!='\0')
{
if(gs[m]=='k')
{
zt[gs[m-1]-48]=1;
bz[gs[m-1]-48]=0;
}
m++;
}
/*情况二，直接判定--否 形如: (D-->aS ,D-->c) */
for(n=0;n<fzg;n++)
{
if(bz[n]==1)
{
m=0;
n2=0;
while(gs[m]!='\0')
{
if(z2[n]==gs[m])
{
if(gs[m+1]>=z1[0]&&gs[m+1]<=z1[n1-1])
zt[n]=0;
else //gs[m+1] 是非终结符n2做标记
}
//跳出循环，无法解决该情况，推到下面情况三
m++;
}
if(n2!=99) //完成所有扫描，未出现非终结符，得出结论zt[n]=0.bz[n]=0不允许再改变zt[n]
}
}
/*情况三，最终判定*/
do
{
flag=0;
for(n=0;n<fzg;n++)
{
if(bz[n]==1) //未得到判定
{ m=0;
while(gs[m]!='\0')
{
if(gs[m]==z2[n]) //判定gs[m]是辅助字符0123
{
m++;
while(gs[m]>='A'&&gs[m]<='Z')
{
n1=0;
for(n2=0;n2<fzg;n2++) //循环查找是gs[m]哪个非终结符
{
if(gs[m]==z[n2])
{
if(zt[n2]==1) //这个非终结符能推出空
zt[n]=1;
else if(bz[n2]==1) //这个非终结符 现在 不能推出空，但它的状态可改即它最终结果还未判定
else
//设 m1 做标记供下一if参考
break; //找到gs[m]是哪个非终结符,for循环完成任务，可以结束
}
}
if(n1==99) break;
m++;
}
}
m++;
}
if(zt[n]==1) bz[n]=0;
if(bz[n]==0) flag=1;//对应for下的第一个if（zt[n]==2）
}
}
}while(flag);
printf("结果是:\n");
for(m=0;m<5;m++)
{
switch(zt[m])
{
case 0:printf("%c---否\n",z[m]);break;
case 1:printf("%c---是\n",z[m]);break;
case 2:printf("%c---未定\n",z[m]);break;
}
}
/*
puts(gs);
puts(zt);
puts(z);
puts(z1);
puts(z2);
printf("%d,,,%d",fzg,zg);
*/
//下面求first集
//下面求first集
for(n=0;n<fzg;n++)
m=0;n=0;n1=0;n2=0;
while(gs[n]>='0'&&gs[n]<='9')
{
for(;m<fzg;m++)
{
if(n2!=m)
n1=0; //m=n2用于第二次以后的for循环中还原上次m的值
if(gs[n]==z2[m])
{
while(gs[n+1]>'9')
{
if(n1==0)
//如果是第一个直接保存
//不是第一个，先与字符数组中其它字符比较，没相同的才保存
else if(gs[n]>='a'&&gs[n]<='z'&&gs[n+1]>='A'&&gs[n+1]<='Z') //gs[n]是终结符 且 gs[n+1]是非终结符
;//什么也不做，程序继续n++，扫描下一个gs[n]
else
{
for(n3=0;n3<=n1;n3++)
{
if(temp[m*13+n3]==gs[n+1])
break;
}
if(n3>n1) //for循环结束是因为n3而不是break
}
n++;
}
break; //break位于if(gs[n]==z2[m]),对于gs[n]已找到z2[m]完成任务跳出for循环
}
}
n2=m; //存放该for循环中m的值
n++;
}
//进一步处理集除去非终结符
m=0;n=0;n1=0;n2=0;
for(m=0;m<fzg;m++)
{
if(flag!=m)
n1=0; //m=flag用于第二次以后的for循环中还原上次m的值
while(temp[m*13+n1]!='\0')
{
while(temp[m*13+n1]>='A'&&temp[m*13+n1]<='Z') //搜索非终结符
{
for(n=0;n<fzg;n++) //确定是哪个非终结符
{if(temp[m*13+n1]==z[n])
break;
}
while(temp[m*13+n1]!='\0') //从temp[n*13+n1]开始每个字符依次往前移动一
n1--;
while(temp[n*13+n2]!='\0') //把z[n]对应的first加入temp[m*13+n1]这个first中，每个字符依次加在最后
{
for(n3=0;n3<n1;n3++) //循环判定是否有相同的字符
{
if(temp[m*13+n3]==temp[n*13+n2])
break;
}
if(temp[n*13+n2]=='k'&&zt[m]==0) //那些不能推出 空，但是因为要加入 其他非终结符的first集 而可能含有 空
n2++;
else if(n3>=n1) //for循环结束是因为n3而不是break ,即无相同字符
else n2++;
}
n1=0;
n2=0;
}
n1++;
}
flag=m; //存放该for循环中m的值
}
//非终结符的first集输出
m=0;n1=0;
for(m=0;m<fzg;m++)
{
n1=0;
printf("非终结符 %c 的first集是: ",z[m]);
while(temp[m*13+n1]!='\0')
{
printf("%c",temp[m*13+n1]);
n1++;
}
printf("\n");
}
}
Ⅲ 编译原理问题
你是长春理工大学的吧?
前几天我们刚写完,一样的.
Ⅳ 编译原理实验二 LL(1)分析法
通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。
根据某一文法编制调试 LL(1)分析程序，以便对任意输入的符号串进行分析。
构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表，对输入符号串自上而下的分析过程。
对文法 的句子进行不含回溯的自上向下语法分析的充分必要条件是：
（1）文法不含左递归；
（2）对于文法中的每一个非终结符 的各个产生式的候选首符集两两不相交，即，若
Follow集合构造：
对于文法 的每个非终结符 构造 的算法是，连续使用下面的规则，直至每个 不再增大为止：
仅给出核心部分
(1) GrammerSymbol.java
(2) GrammerSymbols.java
(3) Grammer.java
(4) LL1Grammer.java
Ⅳ 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。