㈠ 求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]+。
㈩ 编译原理中文法的产生式的左部符号一定是一个非终结符号嘛这话对不
不对的，上下文无关文法和正规式满足这个条件，上下文有关文法和短语文法不满足这个条件。