什麼叫活前綴編譯原理

⑴ 在C++IF語句中如果把if(a＝＝0)寫成if(a＝0)編譯系統有何反應，輸出的結果是什麼

輸出的結果是0。

編譯過程一般是在計算機系統中實現的，是將源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址以及機器代碼。

編譯器是計算機程序中應用比較多的工具，在對編譯器進行前端設計時，一定要充分考慮影響因素，還要對詞法、語法、語義進行分析。編譯原理課程教學理想情況，學生應該能夠獨立自主完成小型編譯系統的構造。

實際教學中，學生只需吃透關鍵的幾條原理知識，如NFA的確定化，LL（1）文法中FIRST和FOLLOW集合的構造，LR（1）文法中識別活前綴DFA構造等，已經滿足了課程考試要求。

⑵ 編譯原理筆記17：自下而上語法分析（4）LR(0)、SLR(1) 分析表的構造

（移進項目就是納凱態指圓點右邊是終結符的項目，規約項目指的就是圓點在右部最右端的項目）

LR(0) 文法可以直接通過識別活前綴的 DFA 來構造 LR 分析表

假定 C = {I ₀ , I ₁ , ... , I _n } （aka. LR(0) 項目規范族、DFA 狀態集）

首先為文法產生式進行編號，拓廣文法的產生式要標記為 0（這里就是後面分析表中 rj 的產生式編號 j 的由來）

然後令每個項目集 I _k 的下標 k 作為分析器洞源的狀態（行首），包含 S' → .S 的集合下標為分析器的初態（也就是 DFA 的初態孫型，一般都是 0 ）。

下面用一個例子來說明 ACTION、GOTO 子表的構造：

SLR(1) 為解決沖突提出了一個簡單的方法：通過識別活前綴的 DFA 和【簡單向前看一個終結符】構造 SLR(1) 分析表。

如果我們的識別活前綴的 DFA 中存在移進-規約沖突、規約-規約沖突，都可以嘗試使用這個方法來解決沖突。（這里說【嘗試】，當然是因為 SLR 也只能解決一部分問題，並不是萬能的靈丹妙葯。。）

這里，我們拿前面那個 LR(0) 解決不了的文法來舉例

該文法不是 LR(0) 文法，但是是 SLR(1) 文法。

觀察上圖 DFA 中的狀態2，想像當我們的自動機正處於這個狀態：次棧頂已經規約為 T 了，棧頂也是當前的狀態 2 ，而當前剩餘輸入為 *。

如果這個自動機不會【往前多看一步】的話，那麼對處於這個狀態的自動機來說，看起來狀態 2 中的移進項目和規約項目都是可選的。這就是移進-規約沖突。

想要解決這個沖突，就輪到【往前多看一步】上場了——把當前剩餘輸入考慮進來，輔助進行項目的選擇：

對其他的沖突也使用同樣的方法進行判斷。

這種沖突性動作的解決辦法叫做 SLR(1) 解決辦法

准備工作部分，與 LR(0) 分析表的構造差不多：同樣使用每個項目集的狀態編號作為分析器的狀態編號，也就同樣用作行下標；同樣使用拓廣文法產生式作為 0 號產生式。

填表也和 LR(0) 類似，唯一的不同體現在對規約項的處理方法上：如果當前狀態有項目 A → α.aβ 和 A → α. ，而次棧頂此時是 α 且讀寫頭讀到的是 a，那麼當且僅當 a∈FOLLOW(A) 時，我們才會用 A → α 對 α 進行規約。

如果構造出來的表的每個入口都不含多重定義（也就是如上圖中表格那樣的，每個格子裡面最多隻有一個動作），那麼該表就是該文法的 SLR(1) 表，這個文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一個 SLR(1) 分析器。

任意的二義文法都不能構造出 SLR(1) 分析表

例：懸空 else

例：

這里的 L 可以理解為左值，R 可以理解為右值

經過計算可以確定其 DFA 如下圖所示。

在 狀態4 中，由於 "=" 同時存在於 FOLLOW(L) 與 FOLLOW(R) 中，因此該狀態內存在移進-規約沖突，故該文法不是 SLR(1) 文法。

這樣的非二義文法可以通過增加向前看終結符的個數來解決沖突（比如LL(2)、LR(2)）但這會讓問題更加復雜，故一般不採用。而二義文法無論向前看多少個終結符都無法解決二義性。

⑶ 編譯原理試題·

Lex和Yacc應用方法(一).初識Lex
草木瓜 20070301
Lex(Lexical Analyzar 詞法分析生成器)，Yacc(Yet Another Compiler Compiler
編譯器代碼生成器)是Unix下十分重要的詞法分析，語法分析的工具。經常用於語言分
析，公式編譯等廣泛領域。遺憾的是網上中文資料介紹不是過於簡單，就是跳躍太大，
入門參考意義並不大。本文通過循序漸進的例子，從0開始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看簡單的例子(註：本文所有實例皆在RetHat linux下完成):
一個簡單的Lex文件 exfirst.l 內容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下執行命令flex解析，會自動生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
進行編譯生成parser可執行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll鏈結選項，cc編譯時會出現以下錯誤，後面會進一步說明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

創建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通過已生成的可執行程序，進行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法會有個直觀的了解：
1.定義Lex描述文件
2.通過lex，flex工具解析成lex.yy.c文件
3.使用cc編譯lex.yy.c生成可執行程序

再來看一個比較完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
進行解析編譯：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
這里就沒有加-ll選項，但是可以編譯通過。下面開始著重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的結構介紹
Lex工具是一種詞法分析程序生成器，它可以根據詞法規則說明書的要求來生成單詞識
別程序，由該程序識別出輸入文本中的各個單詞。一般可以分為<定義部分><規則部
分><用戶子程序部分>。其中規則部分是必須的，定義和用戶子程序部分是任選的。

(1)定義部分
定義部分起始於 %{ 符號，終止於 %} 符號，其間可以是包括include語句、聲明語句
在內的C語句。這部分跟普通C程序開頭沒什麼區別。
%{
#include "stdio.h"
int linenum;
%}
(2) 規則部分
規則部分起始於"%%"符號，終止於"%%"符號，其間則是詞法規則。詞法規則由模式和
動作兩部分組成。模式部分可以由任意的正則表達式組成，動作部分是由C語言語句組
成，這些語句用來對所匹配的模式進行相應處理。需要注意的是，lex將識別出來的單
詞存放在yytext[]字元數據中，因此該數組的內容就代表了所識別出來的單詞的內容。
類似yytext這些預定義的變數函數會隨著後面內容展開一一介紹。動作部分如果有多
行執行語句，也可以用{}括起來。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.規則部分的正則表達式
規則部分是Lex描述文件中最為復雜的一部分，下面列出一些模式部分的正則表達式字
符含義：
A-Z, 0-9, a-z 構成模式部分的字元和數字。
- 指定范圍。例如：a-z 指從 a 到 z 之間的所有字元。
\ 轉義元字元。用來覆蓋字元在此表達式中定義的特殊意義，
只取字元的本身。

[] 表示一個字元集合。匹配括弧內的任意字元。如果第一個字
符是^那麼它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一個。

^ 表示否定。
* 匹配0個或者多個上述模式。
+ 匹配1個或者多個上述模式。
? 匹配0個或1個上述模式。
$ 作為模式的最後一個字元時匹配一行的結尾。
{ } 表示一個模式可能出現的次數。 例如: A{1,3} 表示 A 可
能出現1次或3次。[a-z]{5} 表示長度為5的，由a-z組成的
字元。此外，還可以表示預定義的變數。

. 匹配任意字元，除了 \n。
( ) 將一系列常規表達式分組。如：{Letter}({Letter}|{Digit})*
| 表達式間的邏輯或。
"一些符號" 字元的字面含義。元字元具有。如："*" 相當於 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"後跟有後續表達式，
只匹配模版中"/"前面的部分。如：模式為 ABC/D 輸入 ABCD，
時ABC會匹配ABC/D，而D會匹配相應的模式。輸入ABCE的話，
ABCE就不會去匹配ABC/D。

B.規則部分的優先順序

規則部分具有優先順序的概念，先舉個簡單的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此時，如果輸入內容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析詞法時，是逐個字元進行讀取，自上而下進行規則匹配的，讀取到第一個A字元
時，遍歷後發現三個規則皆匹配成功，Lex會繼續分析下去，讀至第五個字元時，發現
"AAAA"只有一個規則可用，即按行為進行處理，以此類推。可見Lex會選擇最長的字元
匹配規則。
如果將規則
AAAA {printf("THREE\n");};
改為
AAAAA {printf("THREE\n");};
./parser < file1.txt 輸出結果為：
THREE
TWO

再來一個特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
並輸入title，Lex解析完後發現，仍然存在兩個規則，這時Lex只會選擇第一個規則，下面
的則被忽略的。這里就體現了Lex的順序優先順序。把這個例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex編譯時會提示：warning, rule cannot be matched.這時處理title字元時，匹配
到第一個規則後，第二個規則就無效了。
再把剛才第一個例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 顯示效果是一樣的，最後一項規則肯定是會忽略掉的。

C.規則部分的使用變數
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之間，加入了一些類似變數的東西，注意是沒有;的，這表示int，float分
別代指特定的含義，在兩個%%之間，可以通過{int}{float}進行直接引用，簡化模
式定義。

(3) 用戶子程序部分
最後一個%%後面的內容是用戶子程序部分，可以包含用C語言編寫的子程序，而這些子
程序可以用在前面的動作中，這樣就可以達到簡化編程的目的。這里需要注意的是，
當編譯時不帶-ll選項時，是必須加入main函數和yywrap(yywrap將下後面說明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的內部變數和函數
內部預定義變數：
yytext char * 當前匹配的字元串
yyleng int 當前匹配的字元串長度
yyin FILE * lex當前的解析文件，默認為標准輸出
yyout FILE * lex解析後的輸出文件，默認為標准輸入
yylineno int 當前的行數信息
內部預定義宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字元的
默認動作

內部預定義的函數：
int yylex(void) 調用Lex進行詞法分析
int yywrap(void) 在文件(或輸入)的末尾調用。如果函數的返回值是1，就停止解
析。 因此它可以用來解析多個文件。代碼可以寫在第三段，這
樣可以解析多個文件。 方法是使用 yyin 文件指針指向不同的
文件，直到所有的文件都被解析。最後，yywrap() 可以返回1
來表示解析的結束。

lex和flex都是解析Lex文件的工具，用法相近，flex意為fast lexical analyzer generator。
可以看成lex的升級版本。

相關更多內容就需要參考flex的man手冊了，十分詳盡。

四.關於Lex的一些綜述
Lex其實就是詞法分析器，通過配置文件*.l，依據正則表達式逐字元去順序解析文件，
並動態更新內存的數據解析狀態。不過Lex只有狀態和狀態轉換能力。因為它沒有堆棧，
它不適合用於剖析外殼結構。而yacc增加了一個堆棧，並且能夠輕易處理像括弧這樣的
結構。Lex善長於模式匹配，如果有更多的運算要求就需要yacc了。

⑷ 編譯原理求解答案

編譯原理是計算機軟體專業中的非常重要一門課程。例如：如何把我們編寫的高級語言源程序，翻譯成機器可執行的目標程序，這個就需要用到編譯原理技術。

但是學習編譯原理這門課程時，是需要頭腦中對編譯原理課程中涉及到的所有概念必須是相當清楚的，別人才能夠對你的這些問題進行准確的回答。而不是看到這些似曾親切的內容就敢於回答你的內容的。
故我個人的建議還是：你可以向專門講授編譯原理的老師請教你的問題。
以上就是我很多年前學習編譯原理的親身體會。

⑸ 編譯原理中LR（1） 那個向前搜索符怎麼求的 跪求高手解答 復制粘貼或者答非所問的別來

1、首先第一步就是項目[S』-> . S,]，自動生成搜索符]，自動生成搜索符]，自動生成搜索符，從項目[A->α.Bβ,?]生成項目[B->…,first(β)]。

⑹ 有關編譯原理

⑴拓廣文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA ：

⑵ 該文法的 LR(0) 分析表：
狀態 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中沒有沖突狀態。
該文法不是 LR(0) 文法
因為存在沖突狀態： I 4 和 I 7
⑷ SLR(1) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中有沖突狀態，沖突可用 FOLLOW 集解決。
該文法不是 SLR(1) 文法。
因為 FOLLOW(S)={a,b,#} ，所以無法解決沖突