㈠ 求C語言文法及產生式！要做C編譯器——語法分析部分
轉自http://blog.csdn.net/rill_zhen/article/details/7701259http://blog.csdn.net/rill_zhen/article/details/7701259
希望能幫到你
編譯原理-1-C語言的文法
編譯原理-1-C語言的文法
c語言的文法產生式：
program ->
external_declaration
| program external_declaration
external_declaration ->
function_definition
| declaration
function_definition -> type_specifier declarator compound_statement
type_specifier ->
VOID
| CHAR
| INT
| FLOAT
declarator
pointer direct_declarator
| direct_declarator
Pointer->
'*'
| '*' pointer
direct_declarator
IDENTIFIER
|direct_declarator』[『 『]』
|direct_declarator 』[』 constant_expression 』]』
| IDENTIFIER '(' parameter_list ')'
| IDENTIFIER '(' ')'
|direct_declarator『,』identifier_list
identifier_list
: IDENTIFIER
| identifier_list ',' IDENTIFIER
constant_expression->
conditional_expression
parameter_list ->
parameter_declaration
| parameter_list ',' parameter_declaration
parameter_declaration ->
declaration_specifiers IDENTIFIER
compound_statement ->
'{' '}'
| '{' statement_list '}'
| '{' declaration_list statement_list '}'
declaration_list ->
declaration
| declaration_list declaration
Declaration->
init_declarator
| init_declarator_list ',' init_declarator
init_declarator ->
declarator
| declarator '=' initializer
Initializer ->
assignment_expression
| '{' initializer_list '}'
| '{' initializer_list ',' '}'
initializer_list ->
initializer
| initializer_list ',' initializer
statement_list->
statement
| statement_list statement
Statement ->
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
expression_statement ->
';'
| expression ';'
selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
iteration_statement->
WHILE '(' expression ')' statement
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
jump_statement
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
expression
: assignment_expression
| expression ',' assignment_expression
assignment_expression ->
conditional_expression
| unary_expression assignment_operator assignment_expression
conditional_expression ->
logical_or_expression
| logical_or_expression ' ' expression ':' conditional_expression
logical_or_expression ->
logical_and_expression
| logical_or_expression OR_OP logical_and_expression
logical_and_expression
: inclusive_or_expression
| logical_and_expression AND_OP inclusive_or_expression
inclusive_or_expression->
exclusive_or_expression
| inclusive_or_expression '|' exclusive_or_expression
exclusive_or_expression
: and_expression
| exclusive_or_expression '^' and_expression
and_expression
: equality_expression
| and_expression '&' equality_expression
equality_expression
: relational_expression
| equality_expression EQ_OP relational_expression
| equality_expression NE_OP relational_expression
relational_expression
: shift_expression
| relational_expression '$amp;
| relational_expression '$amp;>apos;$ shift_expression
| relational_expression LE_OP shift_expression
| relational_expression GE_OP shift_expression
shift_expression
: additive_expression
| shift_expression LEFT_OP additive_expression
| shift_expression RIGHT_OP additive_expression
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
cast_expression
: unary_expression
| '(' type_name ')' cast_expression
unary_expression
: postfix_expression
| INC_OP unary_expression
| DEC_OP unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
postfix_expression ->
: primary_expression
| postfix_expression '[' expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER
| postfix_expression PTR_OP IDENTIFIER
| postfix_expression INC_OP
| postfix_expression DEC_OP
primary_expression ->
IDENTIFIER
| CONSTANT
| STRING_LITERAL
| '(' expression ')'
argument_expression_list
: assignment_expression
| argument_expression_list ',' assignment_expression
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
assignment_operator ->
'='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
storage_class_specifier ->
TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
struct_or_union_specifier
: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
| struct_or_union '{' struct_declaration_list '}'
| struct_or_union IDENTIFIER
struct_or_union
: STRUCT
| UNION
struct_declaration_list
: struct_declaration
| struct_declaration_list struct_declaration
struct_declaration
: specifier_qualifier_list struct_declarator_list ';'
specifier_qualifier_list ->
type_specifier specifier_qualifier_list
| type_specifier
| type_qualifier specifier_qualifier_list
| type_qualifier
struct_declarator_list ->
struct_declarator
| struct_declarator_list ',' struct_declarator
struct_declarator ->
: declarator
| ':' constant_expression
| declarator ':' constant_expression
enum_specifier ->
ENUM '{' enumerator_list '}'
| ENUM IDENTIFIER '{' enumerator_list '}'
| ENUM IDENTIFIER
enumerator_list ->
enumerator
| enumerator_list ',' enumerator
Enumerator ->
IDENTIFIER
| IDENTIFIER '=' constant_expression
type_qualifier ->
CONST
| VOLATILE
type_qualifier_list ->
type_qualifier
| type_qualifier_list type_qualifier
parameter_type_list ->
parameter_list
| parameter_list ',' ELLIPSIS
parameter_list ->
: parameter_declaration
| parameter_list ',' parameter_declaration
type_name ->
specifier_qualifier_list
| specifier_qualifier_list abstract_declarator
abstract_declarator ->
pointer
| direct_abstract_declarator
| pointer direct_abstract_declarator
direct_abstract_declarator ->
'(' abstract_declarator ')'
| '[' ']'
| '[' constant_expression ']'
| direct_abstract_declarator '[' ']'
| direct_abstract_declarator '[' constant_expression ']'
| '(' ')'
| '(' parameter_type_list ')'
| direct_abstract_declarator '(' ')'
| direct_abstract_declarator '(' parameter_type_list ')'
labeled_statement ->
IDENTIFIER ':' statement
| CASE constant_expression ':' statement
| DEFAULT ':' statement
㈡ 什麼是文法(編譯原理)
【定義】
文法G定義為四元組（VN，VT，P，S）
其中 VN ：非終結符號(即語法變數)集
VT ： 終結符號集
VN∩VT =Φ，令V= VN∪VT，V稱為文法G的字母表或字匯表。
P ：產生式(α→β)集
S ：開始符號，且S∈VN ，S至少要在一條規則的左部出現。
【約定】
一般地，文法G的 四元組 不用全部給出 ，而只將產生式寫出。
約定：
（1）第一條產生式的左部是開始符號
（2）用尖括弧括起來的（或 大寫字母 ）是非終結符號
（3）不用尖括弧括起來（或 小寫字母 ）是終結符號
（4）還有一種習慣寫法，即 G[S] ，其中 S 是 開始符號 。
【舉例】
例: G=（VN，VT，P，S）
其中 VN={S}，
VT ={0，1}，
P={S→0S1，S→01}
S是開始符號
㈢ 編譯原理中的文法的產生式的括弧有什麼用
加上括弧，是讓編程渣談磨語侍悄言機器 最先識別。
就不用 從 E 執行到 F——EIid
先執行 括弧如斗裡面的
㈣ 編譯原理-文法定義
文法定義公式如下:
Chomsky 文法分類將文法分為四種，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。
又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法（Phrase Structure Grammar）
定義: 對於產生式 α→β ， α 至少包含一個非終結符。
為什麼要叫無限制文法，明明它要求產生式的左部必須包含一個非終結符。
又被稱為上下文有關文法(Context-Sensitive Grammar)
定義：對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外
為什麼叫做上下文有關文法？
一般情況下，這種產生式的形式為 α1Aα2→α1βα2
又被稱為上下文無關文法(Context-Free Grammar)
定義：對任一產生式 α→β ，都有 α∈VN，β∈(VN∪VT)*
為什麼叫上下文無關文法？
又被稱為正則文法（Regular Grammar，RG），分為右線性（Right Linear）文法和左線性（Left Linear）文法。
定義: 對任一產生式 α→β ，都有 α∈VN，β最多兩個字元元素，如果有二個字元必須是（終結符+非終結符）的格式，如果是一個字元，那麼必須是終結符。
根據產生式右部非終結符位置不同，分為右線性文法和左線性文法。
可以看出，不同文法就是對產生式進行逐層的限制，所以各個文法是包含關系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最後包含3型文法。
㈤ 關於 編譯原理
一個文法包含四要素：非終結符Vn，終結符Vt，產生式P，起始符S
Vn={S,B,C,D}就是說非終結符有 S、B、C、D
Vt={a,b,c}，終結符有a、b、c
產生式就是P里的那些，比如S可以推出aSBC,S還可以推出abc，CB可以推出CD等
這些是這個文法G1規定好的吧...
㈥ 【編譯原理】第二章：語言和文法
上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。
約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：
產生式
可以簡寫為：
如上例中，
可以簡寫為：
給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。
如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。
推導的反過程稱為 歸約 。
如果 ，則稱 是 的一個 句型（sentential form ）。
由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：
例
文法
表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。
並、連接、冪、克林閉包、正閉包。
如上例表示為：
中必須包含一個 非終結符 。
產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。
上下文有關文法不包含空產生式（ ）。
產生式的一般形式：
即產生式左邊都是非終結符。
右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。
例：（右線性文法）
以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：
正則文法能描述程序設計語言中的多數單詞。
正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。
根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。
給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。
直接短語一定是某產生式的右部，但反之不一定。
如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。
二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。
㈦ 編譯原理中的文法設計這題該怎麼做，能給一下思路和答案嗎
文法的設計需要考慮文法的類型和表達能力。一種可能的思路是：
首先，確定值為非負的5的倍數或3的李臘消倍數的數字串有什麼特徵，例如結尾只能是0或5或3或6或9，不能有前導0等。
然後，選擇合適的文法類型來描述這些特徵，例如正規文法、上下文無關文法等。
最後，根據文法類哪知型的規則，給出局寬產生式和開始符號。
一種可能的答案是：
使用正規文法來描述這個語言。
產生式如下：
開始符號為S。
㈧ 求解編譯原理的一道題:設有文法如下
首先要做這題你要知道判別文法類型
包括四個層次：
0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這里的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
2-型文法生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這里的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。
3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。
正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這里的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。
1）本題應該是--上下文無關文法
句子是產生式在推導時「僅僅有終結符」的任何一步
2）%mm%nn 是一個句子
由於下面一題的圖我等級不夠 不能貼圖 發你郵箱
㈨ (編譯原理) 求下述文法對應正規式： S->0A|1B A->1S|1 B->0S|0
一、簡單的推導思路
1、該文法的對應正規式為：[01|10]+
2、推導：
（1）首先，展開產生式S，可知S要麼以0開頭，要麼以1開頭；
（2）如果S按產生式S->0A展開，則S必以01開頭，因為通過產生式A->1S|1可知，A必定是以1開頭的；
（3）如果S按產生式S->1B展開，則S必以10開頭，因為產生式B必定以0開頭；
（4）綜上，可知，S是以01或10開頭的非終結符號；
（5）當A以產生式A->1展開或 B以B->0展開時，S將推導結束；
（6）當A以產生式A->1S展開或 B以B->0S展開時，產生式中的非終結符號S將重復（1）-（3）的推導步驟；
（7）綜上所述，該文法的對應正規式為：[01|10]+。
二、聯立方程組求解
假設非終結符號S、A、B都分別代表一個正規式，則正規文法的產生式集合所代表的就是關於正規式S、A、B的一個方程組。
我們將文法「|」符號替換為正規式「+」符號，可得，
S=0A+1B=0(1S+1)+1(0S+0)=01(S+ε)+10(S+ε)=(01+10)(S+ε)=(01+10)S+(01+10)。
根據方程X=rX+t有形如X=r*t的解論斷，可得，
S=(01+10)*(01+10)=[01|10]+。
㈩ 編譯原理中文法的產生式的左部符號一定是一個非終結符號嘛這話對不
不對的，上下文無關文法和正規式滿足這個條件，上下文有關文法和短語文法不滿足這個條件。