‘壹’ 求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
‘贰’ 编译器的功能是什么
1、编译器就是将“一种语言（通常为高级语言）”翻译为“另一种语言（通常为低级语言）”的程序。一个现代编译器的主要工作流程：源代码 (source code) → 预处理器 (preprocessor) → 编译器 (compiler) → 目标代码 (object code) → 链接器(Linker) → 可执行程序 (executables)。
2、工作方法：
1）、首先编译器进行语法分析，也就是要把那些字符串分离出来。
2）、然后进行语义分析，就是把各个由语法分析分析出的语法单元的意义搞清楚。
3）、最后生成的是目标文件，也称为obj文件。
4）、再经过链接器的链接就可以生成最后的EXE文件了。
5）、有些时候需要把多个文件产生的目标文件进行链接，产生最后的代码。这一过程称为交叉链接。
‘叁’ 编译器的组成及各部分的功能及作用
1. 词法分析 词法分析器根据词法规则识别出源程序中的各个记号（token），每个记号代表一类单词（lexeme）。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器的输入是源程序，输出是识别的记号流。词法分析器的任务是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。 2. 语法分析 语法分析器根据语法规则识别出记号流中的结构（短语、句子），并构造一棵能够正确反映该结构的语法树。 3. 语义分析 语义分析器根据语义规则对语法树中的语法单元进行静态语义检查，如果类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的。 4. 中间代码生成 中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式，它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码，它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。 5. 中间代码优化 优化是编译器的一个重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上有很大浪费。当需要生成高效目标代码时，就必须进行优化。 6. 目标代码生成 目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。编译器生成的目标程序代码可以有多种形式：汇编语言、可重定位二进制代码、内存形式。 7 符号表管理 符号表的作用是记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的查找和操作。符号表中的某些内容甚至要保留到程序的运行阶段。 8 出错处理用户编写的源程序中往往会有一些错误，可分为静态错误和动态错误两类。所谓动态错误，是指源程序中的逻辑错误，它们发生在程序运行的时候，也被称作动态语义错误，如变量取值为零时作为除数，数组元素引用时下标出界等。静态错误又可分为语法错误和静态语义错误。语法错误是指有关语言结构上的错误，如单词拼写错、表达式中缺少操作数、begin和end不匹配等。静态语义错误是指分析源程序时可以发现的语言意义上的错误，如加法的两个操作数中一个是整型变量名，而另一个是数组名等。
‘肆’ 编译器是什么意思，是做什么的
编译器
编译器是一种特殊的程序，它可以把以特定编程语言写成的程序变为机器可以运行的机器码。我们把一个程序写好，这时我们利用的环境是文本编辑器。这时我程序把程序称为源程序。在此以后程序员可以运行相应的编译器，通过指定需要编译的文件的名称就可以把相应的源文件（通过一个复杂的过程）转化为机器码了。
下面我们看看它是如何工作的。首先编译器进行语法分析，也就是要把那些字符串分离出来。然后进行语义分析，就是把各个由语法分析分析出的语法单元的意义搞清楚。最后生成的是目标文件，我们也称为obj文件。再经过链接器的链接就可以生成最后的可执行代码了。有些时候我们需要把多个文件产生的目标文件进行链接，产生最后的代码。我们把一过程称为交叉链接。
有一个称为LCC的编译器，还挺不错的；还有一个用于分析其规则的小工具；
‘伍’ 编译器的逻辑阶段可以怎样分组
编译器的逻辑阶段通常可以分为以下几个部分：
词法分析（Lexical Analysis）：将源代码转换为单词序列，也称为词法单元或记号。词法分析器将源代码字符流扫描，边扫描边识别记号，然后将这些记号作为输出传递给下一个阶段。识别出的词法单元通常是关键字、标识符、运算符、界符、常量等。
语法分析（Syntax Analysis）：将单词序列转换为语法分析树，也称为语法树。语法分析器通过词法分析器输出的记号序列构建出语法树，检查代码是否符合语法规则。如果发现不符合语法规则的语句，会生成一个错误消息。
语义分析（Semantic Analysis）：对语法树进行语义检查。语义分析器会检查语法树中的语法单元是否符合语义规则，例如变量是否已声明，数据类型是否匹配，函数参数是否正确等。如果发现不符合语义规则的语句，会生成一个错误消息。
中间代码生成（Intermediate Code Generation）：将语法树转换为中间代码。中间代码是一种与源代码无关的代码形式，通常使用一种类似于汇编语言的中间表示形式如伍蠢。
代码优化（Code Optimization）：对中间代码进行优化，以提高程序的性能和效率。代码优化器会应用一些优化技术，例如常量折叠、死代码消除、循环展开等。
目标代码生成（Code Generation）：将中间代码橘配转换为机器码或目标代码。代码生成器会将中间代码转换为目标机器的机器码或汇编代码，以便可执行程序的生成。
符号表管理（Symbol Table Management）：维护变量、函数等符号的信息。符号表管理器会记录符号的类型、作用域、存储位置等信息，并提供符号的查找、插入、删除等操作。
以上是编译器的典型逻辑阶段，不同的编译器可能会渣陪有所不同，但通常都会包含以上阶段的一部分或全部。
‘陆’ C#编写的编译器，实现词法分析和语法分析功能！！求运行文件和代码示例！！
算你强。C#的编译器roslyn开源了，有空你自己去研究下吧。
dotnet/roslyn
https://github.com/dotnet/roslyn
‘柒’ 编译器笔记13-语法分析-LR分析法概述
可以用LR分析法分析的文法可以称为LR分析法。LR文法（ Knuth ，1963）是最大的、可以构造出相应移入- 归约语法分析器的文法类。
LR(k)分析，需要向前查看k个输入符号的LR分析，k=0 和 k=1 这两种情况具有实践意义，当省略(k)时，表示k=1。而在LR(k)这样的名称中，k代表的是分析时所需前瞻符号（lookahead symbol）的数量，也就是除了当前处理到的输入符号之外，还得再向右引用几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。
作为对比这里列出LL(1)文法的含义：
问：自底向上分析的关键问题是什么？
答：如何正确地识别句柄，句柄是逐步形成的，用“状态”表示句柄识别的进展程度。例如在 自底向上分析概述 中所提及到句柄识别错误的例子，通过状态跟下一个输入符号就可以判断出应该做出哪一个动作，而状态相当于一种记忆功能记录当前句柄识别到什么程度。
与移入分析器不同的是LR分析器多了一个与符号栈平行的状态栈。
之后的分析过程与上图类似，直至到如下状态，分析成功。可见分析时进行什么动作是由栈状态栈栈顶的状态和下一个输入符号决定。
输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。
输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。
方法：初始时，语法分析器栈中的内容为初始状态s0 ，输入缓冲区中的内容为w$。然后，语法分析器执行下面的程序：
先了解LR(0)项目和增广文法这两个概念
右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）：A → α1·α2
文法开始符号S表示的是语言中的最大成分。如下图当b出现时可以将它移入到分析栈中。b移进栈后我们期待归约出B。当归约出B时我们还期待再归约一个B。
如果G是一个以S为开始符号的文法，则G的增广文法G'就是在G中加上新开始符号S'和产生式S'→S而得到的文法
引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。
项目可以分为以下几类：
上图中S'对应的第一个项目称为初始项目，而S'对应的最后一个项目称之为接收项目在此状态下文法的开始符号已经被归约出来，因此可以接收了故称为接收项目。红色方框中的项目则被称为归约项目。
项目集闭包(Closure of Item Sets)
可以把等价的项目组成一个项目集(I)，称为项目集闭包，每个项目集闭包对应着自动机的一个状态。
先了解CLOSURE和GOTO这两个函数
项目集I的闭包的数学定义：
返回项目集I对应于文法符号X的后继项目集闭包
规范LR(0)项集族(Canonical LR(0) Collection)
说明： 该自动机的初始状态就是文法的初始项目的项目集闭包，其终止状态集合只有一个状态就是文法的接收项目的项目集闭包。
如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)。不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法。
为了解决移进/归约冲突和归约/归约冲突需要使用到 SLR分析法 和 LR(1)分析法 。
问: 为什么没有移进/移进冲突？
答: 首先只有在移进状态和待约状态下的项目才会有使用到移进操作。在0状态时所有项目都是移进状态根据LL文法显然不会产生移进/移进操作，因为每个产生式左部的SELECT集是没有交集的。而在其他具有待约状态项目的状态中，所有集合都是等价的。假若在某状态下输入终结符y时发生移进/移进冲突，即存在两个这样的项目A0→α0·yβ0，A1→α1·yβ1，但显然这两个项目是不等价的显然与同一状态下所有项目等价相矛盾，因此这种移进/移进冲突是不存在的。假若在某状态下输入非终结符X时发生移进/移进冲突，即存在两个这样的项目A0→α0·Xβ0，A1→α1·Xβ1，而A0与A1在同一状态下是等价的则两项目要么是A0→α0·Xβ0与X→.Xβ1(原项目A1变为X，α1变为ε)要么是A1→α1·Xβ1与X→.Xβ0(原项目A0变为X，α0变为ε)。显然X→Xβ0|Xβ1（左递归）是不符合LL文法的因此这种情况也是不可能出现。
综上移进/移进冲突在LR分析下是不存在的。
‘捌’ 编译原理
编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象[1]。
中文名
编译原理[1]
外文名
Compilers: Principles, Techniques, and Tools[1]
领域
计算机专业的一门重要专业课[1]
快速
导航
编译器
编译原理课程
编译技术的发展
编译的基本流程
编译过程概述
基本概念
编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。[2]
编译器
C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。[3]
C语言编译器前端设计
编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。[3]
1 词法分析[3]
词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。[3]
2 语法分析[3]
语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。[3]
3 语义分析[3]
语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化时, 一定要保证语法结构设置的合法性。在对语法、词法进行检查时, 语法结构设定不合理, 则会出现编译错误的问题。前端设计对精确性要求比较好, 设计人员能够要做好校对工作, 这会影响到编译的准确性, 如果前端设计存在失误, 则会影响C语言编译的效果。[3]