編譯原理構造遞歸下降分析程序
㈠ 高分求編譯原理遞歸下降語法分析設計原理
lz，最好改成這種形式，不要直接消左遞歸：
E -> TAE
T -> FMT
F -> (E) | i
A-> +|- M->*|/
㈡ 編譯原理
FIRST(begin d ；X end)={begin}
FIRST(d ； X)={d}
FIRST(sY)={s}
FIRST(ε)={ε}
FOLLOW(P)={#}
FOLLOW(X)={end}
FOLLOW(Y)={end}
㈢ 求解編譯原理題 構造遞歸下降分析程序
兄弟，其實這個問題不難，只是我感覺你給的問題不完全，不知道怎麼給你解決，要不我給你個遞歸下降分析方法分析文法的例子吧，你先看看。我估計你看了這個後絕對就明白整體的分析思想了～
文法如下:
S->do s1 begin s2 end while s2
s1->s2mB
s2->AmB
A->B
B->VAL //VAL是所有非關鍵字的字元字元組和數字
m->+｜-｜*｜/｜>｜<｜=
/////////////*語法遞歸分析*/////////////////
int B(int * c,int & q)
{
if(c[q]==13)
{ q++;
return 1;
}
else if(c[q]==5)
{ q++;
return 1;
}
else {cout<<"error 'B'"<<endl;return 0;}
}
int A(int * b,int & o)
{
if(B(b,o))
{
return 1;
}
else {cout<<"error 'A'"<<endl;return 0;}
}
int OP(int *r,int & v)
{
if(r[v]==6)
{
v++;
return 1;
}
else if(r[v]==7)
{
v++;
return 1;
}
else if(r[v]==8)
{
v++;
return 1;
}
else if(r[v]==9)
{
v++;
return 1;
}
else if(r[v]==10)
{
v++;
return 1;
}
else if(r[v]==11)
{
v++;
return 1;
}
else if(r[v]==12)
{
v++;
return 1;
}
else {cout<<"error 'OP'"<<endl;return 0;}
}
int S2(int * d,int & h)
{
if(A(d,h))
{
if(OP(d,h))
{
if(B(d,h))
return 1;
else {cout<<"條件語句右部出錯 "<<endl;return 0;}
}
else {cout<<"條件語句缺少運算符 "<<endl;return 0;}
}
else {cout<<"條件語句左部出錯 "<<endl;return 0;}
}
int S1(int * d,int & h)
{
if(S2(d,h))
{
if(OP(d,h))
{
if(B(d,h))
return 1;
else {cout<<"循環語句右部出錯 "<<endl;return 0;}
}
else {cout<<"循環語句缺少運算符 "<<endl;return 0;}
}
else {cout<<"循環語句左部出錯 "<<endl;return 0;}
}
int S(int *a,int & z)
{
if (a[z++]==1)
{
if (S1(a,z))
{
if (a[z++]==2)
{
if (S2(a,z))
{
if(a[z++]==3)
{
if(a[z++]==4)
{
if(S2(a,z))
{
cout<<"語法分析成功!"<<endl;
return 1;
}
else return 0;
}
else {cout<<"error 'while'"<<endl; return 0;}
}
else {cout<<"error 'end'"<<endl; return 0;}
}
else return 0;
}
else {cout<<"error 'begin'"<<endl; return 0;}
}
else return 0;
}
else {cout<<"error 'do'"<<endl; return 0;}
}
/////////////////////// 語法分析結束 ////////////////////////
詞法分析中單詞代號 詞法分析中可識別到的所有單詞
1 do
2 begin
3 end
4 while
5 除關鍵字以外的所有字元或字元串
6 +
7 -
8 *
9 /
10 =
11 >
12 <
13 數字
14 結束標識符「#」
自己好好琢磨琢磨吧，其實思想挺簡單的～
㈣ 用某種高級語言寫出
FIRST(begin d ；X end)={begin}
FIRST(d ； X)={d}
FIRST(sY)={s}
FIRST(ε)={ε}
FOLLOW(P)={#}
FOLLOW(X)={end}
FOLLOW(Y)={end}
㈤ 編譯原理 遞歸下降分析器
自頂向下分析法(遞歸下降分析程序構造)
E-->T/E+T
T-->F/T*F
F-->i/(E)
步驟 棧 輸入字元串 狀態
0 #E i1*(i2+i3)# 初始化
1 #T i1*(i2+i3)# E-->T
2 #T*F i1*(i2+i3)# T-->T*F
3 #T*i i1*(i2+i3)# F-->i
4 #F* *(i2+i3)# 匹配
5 #F (i2+i3)# 匹配
6 #(E) (i2+i3)# E-->(E)
7 #(E i2+i3)# 匹配
8 #(E+T i2+i3)# E-->E+T
9 #(E+F i2+i3)# T-->F
10 #(E+i i2+i3)# F-->i
11 #(E+ +i3)# 匹配
12 #(E i3)# 匹配
13 #(T i3)# E-->T
14 #(F i3)# T-->F
15 #(i i3)# F-->i
16 #( )# 匹配
17 # # 接受
所以可以寫出
PROCEDURE E
BEGIN
T;
WHILE SYM='+' THEN ADVANCE;T END
END;
PROCEDURE T
BEGIN
F;
WHILE SYM='*' THEN ADVANCE;F END
END;
PROCEDURE F
BEGIN
IF SYM='i' THEN ADVANCE END
ELSE
IF SYM='(' THEN
BEGIN ADVANCE;E;
IF SYM=')' THEN ADVANCE;
ELSE ERROR;END
END;
㈥ 編譯遞歸下降分析法
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>
char a[50] ,b[50],d[200],e[10];
char ch;
int n1,i1=0,flag=1,n=5;
int E();
int E1();
int T();
int G();
int S();
int F();
void input();
void input1();
void output();
void main() /*遞歸分析*/
{
int f,p,j=0;
char x;
d[0]='E';
d[1]='=';
d[2]='';
d[3]='T';
d[4]='G';
d[5]='#';
printf("請輸入字元串(長度<50,以#號結束）\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=b[0]=a[0];
printf("文法\t分析串\t\t分析字元\t剩餘串\n");
f=E1();
if (f==0) return;
if (ch=='#')
{ printf("accept\n");
p=0;
x=d[p];
while(x!='#') {
printf("%c",x);p=p+1;x=d[p]; /*輸出推導式*/
}
}
else {
printf("error\n");
printf("回車返回\n");
getchar();getchar();
return;
}
printf("\n");
printf("回車返回\n");
getchar();
getchar();
}
int E1()
{ int f,t;
printf("E--TG\t");
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int E()
{ int f,t;
printf("E--TG\t");
e[0]='E';e[1]='=';e[2]='';e[3]='T';e[4]='G';e[5]='#';
output();
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int T()
{ int f,t;
printf("T--FS\t");
e[0]='T';e[1]='=';e[2]='';e[3]='F';e[4]='S';e[5]='#';
output();
flag=1;
input();
input1();
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);
}
int G()
{ int f;
if(ch=='+') {
b[i1]=ch;
printf("G--+TG\t");
e[0]='G';e[1]='=';e[2]='';e[3]='+';e[4]='T';e[5]='G';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=T();
if (f==0) return(0);
G();
return(1);
}
printf("G--^\t");
e[0]='G';e[1]='=';e[2]='';e[3]='^';e[4]='#';
output();
flag=1;
input();input1();
return(1);
}
int S()
{
int f,t;
if(ch=='*') {
b[i1]=ch;printf("S--*FS\t");
e[0]='S';e[1]='=';e[2]='';e[3]='*';e[4]='F';e[5]='S';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);}
printf("S--^\t");
e[0]='S';e[1]='=';e[2]='';e[3]='^';e[4]='#';
output();
flag=1;
a[i1]=ch;
input();input1();
return(1);
}
int F()
{ int f;
if(ch=='(') {
b[i1]=ch;printf("F--(E)\t");
e[0]='F';e[1]='=';e[2]='';e[3]='(';e[4]='E';e[5]=')';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=E();
if (f==0) return(0);
if(ch==')') {
b[i1]=ch;printf("F--(E)\t");
flag=0;input();input1();
ch=a[++i1];
}
else {
printf("error\n");
return(0);
}
}
else if(ch=='i') {
b[i1]=ch;printf("F--i\t");
e[0]='F';e[1]='=';e[2]='';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];
}
else {printf("error\n");return(0);}
return(1);
}
void input()
{
int j=0;
for (;j<=i1-flag;j++)
printf("%c",b[j]); /*輸出分析串*/
printf("\t\t");
printf("%c\t\t",ch); /*輸出分析字元*/
}
void input1()
{
int j;
for (j=i1+1-flag;j<n1;j++)
printf("%c",a[j]); /*輸出剩餘字元*/
printf("\n");
}
void output(){ /*推導式計算*/
int m,k,j,q;
int i=0;
m=0;k=0;q=0;
i=n;
d[n]='=';d[n+1]='';d[n+2]='#';n=n+2;i=n;
i=i-2;
while(d[i]!=''&&i!=0) i=i-1;
i=i+1;
while(d[i]!=e[0]) i=i+1;
q=i;
m=q;k=q;
while(d[m]!='') m=m-1;
m=m+1;
while(m!=q) {
d[n]=d[m];m=m+1;n=n+1;
}
d[n]='#';
for(j=3;e[j]!='#';j++){
d[n]=e[j];
n=n+1;
}
k=k+1;
while(d[k]!='=') {
d[n]=d[k];n=n+1;k=k+1;
}
d[n]='#';
}
這是我們用到的程序，看看對你有沒有幫助。
至於下面的兩個問題，很簡單，可以容易做出來吧！
不會可以和我交流！
祝 進步！
㈦ 編譯原理，遞歸下降子程序語法分析
沒學過編譯原理，看描述，是讓寫一個腳本執行軟體。
終結符我查了下，就是不可再分的。比如iε。
輸入是EGTSFI*/ε組成的字元串。
規則需要預處理。注意轉意符在字元串中的效果。因為有/字元。
不會c或c++，只會c#。你可以到貼吧發帖。強人工智慧吧 就挺好。演算法吧有點亂。
最重要的，不要錢。
㈧ 編譯原理,急
1. L(A)|L(A)=L(A) => A|A=A 2. A=b|aA => L(A)= {b或任意個a開頭，以b結束的字元串} => A=a*b 同理：A=a*b => A=b|aA 所以：A=b|aA當且僅當A=a*b 3. ....有點麻煩
㈨ 編譯原理：構造產生此語言的上下文無關文法G
對於文法G=(V, T, S, P)，如果產生式的形式如下：
A -> xB
A -> x
其中A, B屬於V，x屬於T*，則稱為右線性文法；相似的，如果產生式的形式如下：
A -> Bx
A -> x
則稱為左線性文法。右線性文法和左線性文法統稱為正則文法。
正則表達式的表達能力等價於正則文法，正則表達式的定義如下：
字母表中的任意字母是正則表達式，空串和空集也是正則表達式；
如果r, s是正則表達式，那麼r|s, rs, r*, (r)也是正則表達式。
正則表達式的擴展：
r+：一個或多個重復
. ：任意字元
[a-z]：字元范圍
[^abc]：不在給定集合中的任意字元
r?：可選
正則表達式只能使用終結符（字母表中的字元），因而很容易變得復雜又難懂，實際中，經常使用正則描述，正則描述允許使用非終結符定義表達式，很像EBNF，但是它限制在未完全定義之前，不能使用非終結符，也就是說不允許遞歸或自嵌套。
像正則表達式的表達能力等價於正則文法一樣，BNF範式的表達能力等價於上下文無關文法。BNF是「Backus Naur Form」的縮寫。John Backus和Peter Naur首次引入一種形式化符號來描述給定語言的語法。
BNF的元符號：
::= 表示「定義為 」，有的書上用-->
| 表示「或者」
< > 尖括弧用於括起非終結符。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如上所述，上下文無關文法的遞歸性，對其分析方法也有很大影響。首先，用作識別這些結構的演算法必須使用遞歸調用或顯式管理的分析棧。其次，用作表示語言語義結構的數據結構現在也必須是遞歸的（通常是一顆分析樹），而不再是線性的（如同用於詞法和記號中的一樣）了。
在程序設計語言中，通常用正則表達式描述詞法規則。但是正則表示式的表達能力有限，她無法表達括弧配對等語法形式，因而，需要引入表達能力更強的上下文無關文法。編譯程序中常用正則文法表示詞法，用上下文無關文法表示語法。那麼程序語言中那些屬於詞法哪些屬於語法呢？一個簡單的辦法，把所有能用正則文法表示的規則成為詞法，即我們用盡可能的使用正則文法表示更多的東西，那些無法用正則表示式表示的成為句法，如C語言中的{ statement; }語法形式。語言中有些規則使用上下文無關文法仍然無法描述，例如變數的定義在使用之前，類型匹配等等，這些通常稱為（靜態）語義，它們在編譯程序的靜態語義檢查階段進行檢測。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。