編譯原理cfg設計

Ⅰ 編譯原理-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(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。

Ⅱ 編譯原理課程設計

%{

/* FILENAME: C.Y */

%}
#define YYDEBUG_LEXER_TEXT (yylval) /* our lexer loads this up each time */
#define YYDEBUG 1 /* get the pretty debugging code to compile*/
#define YYSTYPE char * /* interface with flex: should be in header file */
/* Define terminal tokens */
/* keywords */
%token AUTO DOUBLE INT STRUCT
%token BREAK ELSE LONG SWITCH
%token CASE ENUM REGISTER TYPEDEF
%token CHAR EXTERN RETURN UNION
%token CONST FLOAT SHORT UNSIGNED
%token CONTINUE FOR SIGNED VOID
%token DEFAULT GOTO SIZEOF VOLATILE
%token DO IF STATIC WHILE
/* ANSI Grammar suggestions */
%token IDENTIFIER STRINGliteral
%token FLOATINGconstant INTEGERconstant CHARACTERconstant
%token OCTALconstant HEXconstant
/* New Lexical element, whereas ANSI suggested non-terminal */
%token TYPEDEFname /* Lexer will tell the difference between this and
an identifier! An identifier that is CURRENTLY in scope as a
typedef name is provided to the parser as a TYPEDEFname.*/
/* Multi-Character operators */
%token ARROW /* -> */
%token ICR DECR /* ++ -- */
%token LS RS /* << >> */
%token LE GE EQ NE /* <= >= == != */
%token ANDAND OROR /* && || */
%token ELLIPSIS /* ... */
/* modifying assignment operators */
%token MULTassign DIVassign MODassign /* *= /= %= */
%token PLUSassign MINUSassign /* += -= */
%token LSassign RSassign /* <<= >>= */
%token ANDassign ERassign ORassign /* &= ^= |= */
%start translation_unit
%%
/* CONSTANTS */
constant:
INTEGERconstant
| FLOATINGconstant
/* We are not including ENUMERATIONconstant here because we
are treating it like a variable with a type of "enumeration
constant". */
| OCTALconstant
| HEXconstant
| CHARACTERconstant
;

string_literal_list:
STRINGliteral
| string_literal_list STRINGliteral
;
/************************* EXPRESSIONS ********************************/
primary_expression:
IDENTIFIER /* We cannot use a typedef name as a variable */
| constant
| string_literal_list
| '(' comma_expression ')'
;
postfix_expression:
primary_expression
| postfix_expression '[' comma_expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression {} '.' member_name
| postfix_expression {} ARROW member_name
| postfix_expression ICR
| postfix_expression DECR
;
member_name:
IDENTIFIER
| TYPEDEFname
;
argument_expression_list:
assignment_expression
| argument_expression_list ',' assignment_expression
;
unary_expression:
postfix_expression
| ICR unary_expression
| DECR unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
;
unary_operator:
'&'
| '*'
| '+'
| '-'
| '~'
| '!'
;
cast_expression:
unary_expression
| '(' type_name ')' cast_expression
;
multiplicative_expression:
cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
;
additive_expression:
multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
;
shift_expression:
additive_expression
| shift_expression LS additive_expression
| shift_expression RS additive_expression
;
relational_expression:
shift_expression
| relational_expression '<' shift_expression
| relational_expression '>' shift_expression
| relational_expression LE shift_expression
| relational_expression GE shift_expression
;
equality_expression:
relational_expression
| equality_expression EQ relational_expression
| equality_expression NE relational_expression
;
AND_expression:
equality_expression
| AND_expression '&' equality_expression
;
exclusive_OR_expression:
AND_expression
| exclusive_OR_expression '^' AND_expression
;
inclusive_OR_expression:
exclusive_OR_expression
| inclusive_OR_expression '|' exclusive_OR_expression
;
logical_AND_expression:
inclusive_OR_expression
| logical_AND_expression ANDAND inclusive_OR_expression
;
logical_OR_expression:
logical_AND_expression
| logical_OR_expression OROR logical_AND_expression
;
conditional_expression:
logical_OR_expression
| logical_OR_expression '?' comma_expression ':'
conditional_expression
;
assignment_expression:
conditional_expression
| unary_expression assignment_operator assignment_expression
;
assignment_operator:
'='
| MULTassign
| DIVassign
| MODassign
| PLUSassign
| MINUSassign
| LSassign
| RSassign
| ANDassign
| ERassign
| ORassign
;
comma_expression:
assignment_expression
| comma_expression ',' assignment_expression
;
constant_expression:
conditional_expression
;
/* The following was used for clarity */
comma_expression_opt:
/* Nothing */
| comma_expression
;
/******************************* DECLARATIONS *********************************/
/* The following is different from the ANSI C specified grammar.
The changes were made to disambiguate typedef's presence in
declaration_specifiers (vs. in the declarator for redefinition);
to allow struct/union/enum tag declarations without declarators,
and to better reflect the parsing of declarations (declarators
must be combined with declaration_specifiers ASAP so that they
are visible in scope).
Example of typedef use as either a declaration_specifier or a
declarator:
typedef int T;
struct S { T T;}; /* redefinition of T as member name * /
Example of legal and illegal statements detected by this grammar:
int; /* syntax error: vacuous declaration * /
struct S; /* no error: tag is defined or elaborated * /
Example of result of proper declaration binding:
int a=sizeof(a); /* note that "a" is declared with a type in
the name space BEFORE parsing the initializer * /
int b, c[sizeof(b)]; /* Note that the first declarator "b" is
declared with a type BEFORE the second declarator is
parsed * /
*/
declaration:
sue_declaration_specifier ';'
| sue_type_specifier ';'
| declaring_list ';'
| default_declaring_list ';'
;
/* Note that if a typedef were redeclared, then a declaration
specifier must be supplied */
default_declaring_list: /* Can't redeclare typedef names */
declaration_qualifier_list identifier_declarator {} initializer_opt
| type_qualifier_list identifier_declarator {} initializer_opt
| default_declaring_list ',' identifier_declarator {} initializer_opt
;

declaring_list:
declaration_specifier declarator {} initializer_opt
| type_specifier declarator {} initializer_opt
| declaring_list ',' declarator {} initializer_opt
;

declaration_specifier:
basic_declaration_specifier /* Arithmetic or void */
| sue_declaration_specifier /* struct/union/enum */
| typedef_declaration_specifier /* typedef*/
;

type_specifier:
basic_type_specifier /* Arithmetic or void */
| sue_type_specifier /* Struct/Union/Enum */
| typedef_type_specifier /* Typedef */
;

declaration_qualifier_list: /* const/volatile, AND storage class */
storage_class
| type_qualifier_list storage_class
| declaration_qualifier_list declaration_qualifier
;

type_qualifier_list:
type_qualifier
| type_qualifier_list type_qualifier
;

declaration_qualifier:
storage_class
| type_qualifier /* const or volatile */
;

type_qualifier:
CONST
| VOLATILE
;

basic_declaration_specifier: /*Storage Class+Arithmetic or void*/
declaration_qualifier_list basic_type_name
| basic_type_specifier storage_class
| basic_declaration_specifier declaration_qualifier
| basic_declaration_specifier basic_type_name
;

basic_type_specifier:
basic_type_name /* Arithmetic or void */
| type_qualifier_list basic_type_name
| basic_type_specifier type_qualifier
| basic_type_specifier basic_type_name
;

sue_declaration_specifier: /* Storage Class + struct/union/enum */
declaration_qualifier_list elaborated_type_name
| sue_type_specifier storage_class
| sue_declaration_specifier declaration_qualifier
;

sue_type_specifier:
elaborated_type_name /* struct/union/enum */
| type_qualifier_list elaborated_type_name
| sue_type_specifier type_qualifier
;

typedef_declaration_specifier: /*Storage Class + typedef types */
typedef_type_specifier storage_class
| declaration_qualifier_list TYPEDEFname
| typedef_declaration_specifier declaration_qualifier
;

typedef_type_specifier: /* typedef types */
TYPEDEFname
| type_qualifier_list TYPEDEFname
| typedef_type_specifier type_qualifier
;

storage_class:
TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
;

basic_type_name:
INT
| CHAR
| SHORT
| LONG
| FLOAT
| DOUBLE
| SIGNED
| UNSIGNED
| VOID
;

elaborated_type_name:
aggregate_name
| enum_name
;

aggregate_name:
aggregate_key '{' member_declaration_list '}'
| aggregate_key identifier_or_typedef_name
'{' member_declaration_list '}'
| aggregate_key identifier_or_typedef_name
;

Ⅲ 編譯原理中的cfg是什麼的縮寫

上下文無關文法（英語：context-free grammar，縮寫為 CFG）

Ⅳ 編譯原理課程－簡單詞法分析器設計（C或C++）

分類: 電腦/網路 >> 程序碰陵設計 >> 其他編程語言
問題描述:

完成以下正則文法所描述的Pascal語言子集單詞符號的詞法分析程序。

<標識符>→字母｜ <標識符>字母｜ <標識符>數字

<無符號整數>→數字｜ <無符號整數>數字

<單字元分界符> →+ ｜－ ｜* ｜; ｜(｜)

<雙字元分界符>→<大於>=｜<小於>=｜<小於>>｜<冒號>=｜<斜豎>*

<小於>→<

<等於>→=

<大於>→>

<冒號> →:

<斜豎> →/

該語言的保留字 ：begin end if then else for do while and or not

說明：

1 該語言大小寫不敏感。

2 字母為a-z A-Z，數字為0-9。

3可以對上述文法進行擴充和笑坦戚改造。

4 『/*……*/』為程序的注釋部分。

[設計要求]

1、 給出各單詞符號的類別編碼。

2、 詞法分析程序應能發現輸入串中的錯誤。

3、 詞法分析作為單獨一遍編寫，詞法分析結果為二元式序列組成的中間文件。

4、設計兩個測試用例（信宴盡可能完備），並給出測試結果。

解析:

這種問題 …… 會有人解答嗎?

Ⅳ 編譯原理 文法類型

    0型文法(Type-0 Grammar)

    1型文法(Type-1 Grammar)

    2型文法(Type-2 Grammar)

    3型文法(Type-3 Grammar)

無限制文法(Unrestricted Grammar) /短語結構文法(Phrase Structure Grammar, PSG )

∀α → β∈P， α中至少包含1個非終結符

0型語言

由0型文法G生成的語言L(G )

上下文有關文法(Context-Sensitive Grammar , CSG )

∀α → β∈P，｜α｜≤｜β｜

產生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )

上下文有關語言（1型語言）

由上下文有關文法(1型文法) G生成的語言L(G )

上下文無關文法(Context-Free Grammar, CFG )

∀α → β∈P，α ∈ VN

產生式的一般形式：A→β

上下文無關語言（2型語言）

由上下文無關文法(2型文法) G生成的語言L(G )

正則文法(Regular Grammar, RG )

右線性(Right Linear)文法： A→wB 或 A→w

左線性(Left Linear) 文法： A→Bw 或 A→w

左線性文法和右線性文法都稱為正則文法

0型文法：α中至少包含1個非終結符

1型文法（CSG） ：｜α｜≤｜β｜

2型文法（CFG） ：α ∈ VN

3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)

0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法

Ⅵ 編譯原理課程設計－詞法分析器設計（C語言）

#include"stdio.h"/*定義I/O庫所用的某些宏和變數*/

#include"string.h"/*定義字元串庫函數*/

#include"conio.h"/*提供有關屏幕窗口操作函數*/

#include"ctype.h"/*分類函數*/

charprog[80]={''},

token[8];/*存放構成單詞符號的字元串*/

charch;

intsyn,/*存放單詞字元的種別碼*/

n,

sum,/*存放整數型單詞*/

m,p;/*p是緩沖區prog的指針，m是token的指針*/

char*rwtab[6]={"begin","if","then","while","do","end"};

voidscaner(){

m=0;

sum=0;

for(n=0;n<8;n++)

token[n]='';

ch=prog[p++];

while(ch=='')

ch=prog[p++];

if(isalpha(ch))/*ch為字母字元*/{

while(isalpha(ch)||isdigit(ch))/*ch為字母字元或者數字字元*/{

token[m++]=ch;

ch=prog[p++];}

token[m++]='';

ch=prog[p--];

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)/*字元串的比較*/{

syn=n+1;

break;}}

else

if(isdigit(ch))/*ch是數字字元*/{

while(isdigit(ch))/*ch是數字字元*/{

sum=sum*10+ch-'0';

ch=prog[p++];}

ch=prog[p--];

syn=11;}

else

switch(ch){

case'<':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='>'){

syn=21;

token[m++]=ch;}

elseif(ch=='='){

syn=22;

token[m++]=ch;}

else{

syn=20;

ch=prog[p--];}

break;

case'>':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=24;

token[m++]=ch;}

else{

syn=23;

ch=prog[p--];}

break;

case':':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=18;

token[m++]=ch;}

else{

syn=17;

ch=prog[p--];}

break;

case'+':syn=13;token[0]=ch;break;

case'-':syn=14;token[0]=ch;break;

case'*':syn=15;token[0]=ch;break;

case'/':syn=16;token[0]=ch;break;

case'=':syn=25;token[0]=ch;break;

case';':syn=26;token[0]=ch;break;

case'(':syn=27;token[0]=ch;break;

case')':syn=28;token[0]=ch;break;

case'#':syn=0;token[0]=ch;break;

default:syn=-1;}}

main()

{

printf(" Thesignificanceofthefigures: "

"1.figures1to6saidKeyword "

"2. "

"3.figures13to28saidOperators ");

p=0;

printf(" pleaseinputstring: ");

do{

ch=getchar();

prog[p++]=ch;

}while(ch!='#');

p=0;

do{

scaner();

switch(syn){

case11:printf("(%d,%d) ",syn,sum);break;

case-1:printf(" ERROR; ");break;

default:printf("(%d,%s) ",syn,token);

}

}while(syn!=0);

getch();

}

程序測試結果

對源程序beginx:=9:ifx>9thenx:=2*x+1/3;end#的源文件，經過詞法分析後輸出如下圖5-1所示：

具體的你在修改修改吧

Ⅶ 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

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

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

Ⅷ 編譯原理筆記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 中，給表達式加括弧：

Ⅸ 編譯原理 詞法分析程序的設計與實現實驗題

說他像蒼蠅，是罵蒼蠅呢還是罵他呢？

Ⅹ 編譯原理課程設計-----語法高亮轉換軟體

IDE之所以能夠語法著色，是因為IDE環境帶有詞法分析功能，然後根據詞法分析結果分別用不同顏色來顯示代碼。要放到網頁上也帶有語法著色，就需要做一個詞法分析器。

詞法分析器其實很簡單，不過很繁瑣。技術含量不高，但是工作量比較大。

我做過C++代碼的詞法分析器，用VC做的，用於模擬魔獸地圖編輯器的那種游戲引擎的腳本設計系統。

總體思路，其實，詞法分析就是把一個一個的單胡唯孝詞分開，有現成的詞法分析代碼生成工具，比如LEX。不過，自己動手寫一個也不難，說白了，他就是一個有窮自動機。

要實現你所說的功能，就是將輸入的褲稿代碼進行詞山帆法分析之後，根據詞法分析的結果，將token（就是正確斷字後的單詞）分別用不同的顏色描述出來。其實就是在token的前後插入HTML語言的顏色控制代碼。

比如：
輸入：if( a = b )
分析過程：[/keyword]if[/keywordend][/operator]([/operatorend][/ident]a[/identend][/operator]=[/operatorend][/ident]b[/ident][/operator])[/operatorend]
輸出：[/textcolor:00ff0000]if[/textcolor] .............