编译原理文法分析回溯怎么解题

⑴ 编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

那么如何进行改造呢？
其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

⑵ 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。

例：

总是选择每个句型的 最左非终结符 进行替换。

总是选择每个句型的 最右非终结符 进行替换。

在自底向上的分析中，总是采用 最左规约 的方式，因此把 最左规约 称为 规范规约 ，对应的 最右推导 称为 规范推导 。

最左推导、最右推导具有唯一性。

自顶向下的语法分析采用最左推导方试，总是选择每个句型的 最左非终结符 进行替换。

由一组 过程 组成，每一个过程对应一个 非终结符 。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。

如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为 回溯 。

预测分析 是 递归下降分析 技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法 。

预测分析不需要回溯，具有确定性。

含有 形式产生式的文法称为是 直接左递归 的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是 左递归 的。其中，经过两步或以上推导产生的左递归，称为 间接左递归 的。
左递归会使递归下降分析器陷入无限循环。

文法
即
该文法是直接左递归的，会陷入无限循环。

将以上文法转换为：


即可消除左递归。事实上，这个过程把左递归转换成了右递归。

消除直接左递归的一般形式

使用代入法。

对于一个文法，通过改写产生式来 推迟决定 ，等获得足够多的输入信息再做正确的决定。

例：文法：

可以改写为：

从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定型文法）

可能在某个举行中紧跟在A后面的终结符a的集合，记为 FOLLOW(A) 。
如果A是某个句型的最右符号，则将结束符“ $ ”添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符号串α串首终结符的集合，记作 FIRST(A) 。

⑶ 回溯法的用回溯法解题的一般步骤

（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法C语言举例
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而着名的问题。该问题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇后问题的皇后所在每一行位置，从1开始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are: );
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish && i<Queens+1) //处理未结束
{
for(flag=1,k=1;flag && k<i;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判断是否有多个皇后在对角线
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重设第i个元素
{
if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值
{
i--; //退回一步 重新试探处理前一个元素
if(i>1 && a[i]==Queens)
a[i]=1; // 当a[i]为 Queens时 将a[i]的值重置
else
if(i==1 && a[i]==Queens)//当第一未位的值达到Queens时结束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一个元素的值为Queens
if(a[i-1]==Queens)
a[i]=1;
else //否则元素为前一个元素的下一个值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]:: [%2d]:,count);
for(k=1;k<=Queens;k++) //输出结果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通过路径用数字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf( );
}
system(pause);
return 0;
}
回溯法解决迷宫问题PASCAL语言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.

⑷ 编译原理 设文法G[S] 求答案！

1. ·消除左递归 S→aAS'|∧aAS'
   S'→VaAS'|ε

   对A的产生式提取左因子 A→∧aA' A'→A|ε

2. · 非终结符合 First Follow

S a∧ #

S’ V ε #

A ∧ #

A‘ ∧ #

Select（S→aAS'）=a

Select(S→∧aAS')=∧

Select(S'→VaAS')=V

Select(S'→ε)=#

Select(A→∧aA')=∧

Select(A'→A)=∧

Select(A'→ε)=#

符合LL（1）文法

a ∧ V #

S S→aAS' S→∧aAS'

S' S'→VaAS' S'→ε

A A→∧aA'

A' A'→A A'→ε

⑸ 编译原理文法题 求解

一看就是计科的 …………
我们都是 LL1 SLR1文法没怎么用过
进来问候下
有空加个好友 讨论下

⑹ 回溯的在编译原理中的运用

如左图，在发生虚假匹配时需要进行回溯，就是退回到开始的位置

⑺ 编译原理实验二 LL(1)分析法

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

根据某一文法编制调试 LL(1)分析程序，以便对任意输入的符号串进行分析。
构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表，对输入符号串自上而下的分析过程。

对文法 的句子进行不含回溯的自上向下语法分析的充分必要条件是：
（1）文法不含左递归；
（2）对于文法中的每一个非终结符 的各个产生式的候选首符集两两不相交，即，若

Follow集合构造：
对于文法 的每个非终结符 构造 的算法是，连续使用下面的规则，直至每个 不再增大为止：

仅给出核心部分
(1) GrammerSymbol.java

(2) GrammerSymbols.java

(3) Grammer.java

(4) LL1Grammer.java

⑻ 编译原理问题，求解决

去问下医生是怎么回事吧

⑼ 编译原理回溯

消除回溯：提取左公因子a,（注：用e代表一补西农符号,就是反三的那个符号,在电脑上不知道怎么打那个符号）
S→aS'|(L)
S'→S|e
消除左递归：
L→SL'
L'→,SL'|e (注意S前面有一个符号“,”)

⑽ 求一道编译原理文法的题目的解法]

1. S->(L)|aS|a
L->SL'
L'->SL'|空
2. first:
S: ( ,a
L: ( ,a
L':( ,a,空

follow:
S: ( , a , $
L: )
L': )

仓促写的...