公共语言运行时的一个简单编译器
4.89/5 (81投票s)
2003年5月6日
9分钟阅读
307925
5143
一个端到端的示例，
引言
有些人可能会想，为什么有人会费力去写一个编译器，因为市面上已经有很多优秀的编译器了。答案很简单，你可能永远不需要自己写编译器，但很有可能你会发现自己处于一个可以应用许多构建编译器所涉及的思想和算法的场景中。此外，用自己的语言编写程序（保证就业）还是挺酷的。
编程语言之所以被称为语言，是有原因的，因为它们实际上就是语言。编程语言由一组标记（相当于英语中的单词）和产生式（语法规则）定义。编程语言与自然语言的主要区别在于，自然语言可能有多种解释，而编程语言则不能。每次构建程序都以不同的方式编译，那将非常无趣。可以有多种解释的语言称为歧义语言，对我们没有用。
警告
关于这方面的内容，已经写了整本书，我无法在这篇文章中解释这个项目中的 5000 多行代码，而且说实话，我也不想。强烈建议你对语法和自底向上解析技术有一些背景知识，并了解一些 MSIL 知识。我尤其为 Scanner.cs 和 Parser.cs 中的代码感到自豪，这包含了整个项目的核心，其余的只是必要的繁琐工作。不用费心去看 Generator.cs 文件，那是我的疏忽和在这个学校项目上的疲惫之作。
一种简单的语言
一组标记和一组规则定义了一种语言。如果可以使用语言的标记和规则推导出某个文本，则称该文本是符合语法的。描述所有二进制数的语言可以如下描述：
L = {标记(0,1), 规则(任意数量的0或1)}
现在我们可以问一下，文本“1200011”是否符合语法？答案应该是否定的，因为我们看到了“2”，它不是我们语言的一部分标记。
语言这个话题值得深入探讨，我还没有准备好，也不知道如何完全解释，所以请大家自行搜索。
正则表达式
正则表达式用于描述简单的语言，通常是标记本身，或者是电话号码或社会安全号码之类的内容。正则表达式“A*BC”可以转化为更冗长的语言定义 L {标记(A,B,C), 规则(零个或多个A，后跟一个B，然后一个C)}。这很好，但是我们如何编写一个程序，使用正则表达式来判断字符流是否符合语法？该问题的通用解决方案是根据给定的正则表达式创建一个非确定性有限状态自动机 (NFA)，然后将此 NFA 转换为确定性有限状态自动机 (DFA)。如果您以前从未听说过这些，请不用担心，在本文的其余部分您将不会遇到它们。DFA 简单来说就是一个状态机，确定性的意思是，从任何一个状态出发，根据输入字符，您只能进入另一个特定的状态。考虑以下正则表达式；
R = int|char|ch
该正则表达式对应的 DFA 如下：
一旦我们有了 DFA，我们就可以轻松地编写一个算法来检查字符是否符合语法。考虑以下字符串：
interop
我们从状态 0（起始状态）开始，读取第一个字符“i”，这会将我们带到状态 1。然后我们读取下一个字符“n”，这会将我们带到状态 2，下一个字符“t”会将我们带到状态 3，这是一个接受状态，但我们还没有读取完整个字符串。下一个字符“e”将我们带到任何地方，实际上是带到一个错误状态，这表明字符串不符合语法。
char
第一个字符“c”将我们带到状态 4，下一个字符将我们带到状态 5，然后“a”将我们带到状态 6，最后“r”将我们带到状态 7。我们已经读取完整个字符串，所以我们检查当前状态（状态 7）是否为接受状态，在这种特定情况下，它是，它接受 char。因此，该字符串符合语法。
cin
第一个字符“c”将我们带到状态 4。下一个字符“i”并不能将我们带到任何地方，除了错误状态。该字符串不符合语法。
语法
语法与正则表达式一样，都用于描述语言。但是，语法比正则表达式强大得多。我将不深入探讨语法，因为内容太多了。简而言之，语法是一组由终结符和非终结符组成的产生式（规则）。终结符是标记。非终结符是包含终结符和非终结符的语法元素。
定义所有嵌套括号语言的典型语法示例如下：
1 : S -> (S)
2 : S ->
在这种情况下，“(”和“)”是语言的标记，S 是唯一的非终结符。产生式 1 告诉我们 S 可以是“（”后跟 S 再后跟“）”。产生式 2 告诉我们 S 可以是空。为了更好地可视化，让我们以字符串“((()))”为例。我们可以使用产生式 2 将最内层的空位置替换为 S，现在我们得到 (((S)))。使用产生式 1，我们可以将最内层的 (S) 替换为 S 来得到 ((S))，重复此步骤得到 (S) 最终得到 S。困难在于尝试确定何时以及使用哪个产生式。这方面有很多理论知识，我并不完全理解，因此不想深入探讨。
我之所以略过所有难点，是因为有编译器工具可以创建 DFA 和 LALR 表。所以我们不需要过多关注它是如何完成的。大多数编译器工具实际上会生成 C++/Java/C# 代码，本项目中使用的工具会生成一个包含表的文件的。这个工具叫做 Gold Parser。别觉得你在作弊，没有这样的工具，几乎不可能写出一个自底向上解析器。
Sharp 编译器
老实说，由于我不想花几天时间写这篇文章，我将基于我的学校项目，我称之为 Sharp。Sharp 是一种非常简单的语言，包含一些基本功能；整数基元、整数数组、if for do while 语句、复杂表达式、函数、通过引用或值传递函数参数、函数内嵌套函数、用于输入和输出的函数以及其他一些很棒的功能。下面是该语言外观的概览。
用 Sharp 实现的冒泡排序
module Bubble_Sort
{
/* Global Variables */
int size = Read();
int [] array = new [size];
int i;
/* Initialize Array */
for(set i = 0;i < size;set i = i + 1)
{
set array[i] = Read();
}
Sort();
/* Display sorted array */
for(set i = 0;i < size;set i = i + 1)
{
Write(array[i]);
}
Read();
return;
/* Simple bubble sort routine */
void Sort()
{
int sorting = 1;
int temp;
while(sorting)
{
set sorting = 0;
for(set i = 0; i < (size - 1); set i = i + 1)
{
if(array[i] > array[i+1])
{
set temp = array[i];
set array[i] = array[i+1];
set array[i+1] = temp;
set sorting = 1;
}
}
}
return;
}
}
最初设计语言语法时，我贪多嚼不烂。并非语法中出现的所有内容都已实现。例如结构体或其他基本类型尚未实现，数组传递也尚未实现。
Organization
在上面的源代码下载中，您会注意到两个项目：Magic IDE 和 Core。Magic IDE 是一个简单的 IDE，提供项目管理功能，尽管编译器只能构建单个文件。Magic IDE 使用了两个非我创建的组件：IC#Code TextEditor 和出色的 Magic Library。Core 包含编译器源代码，它提供了 5 个主要类：Language、Scanner、Parser、Semantics、Generator。
Language 类是对 Gold Parser 生成文件的包装，它读取该文件并使其内容更易于访问。Scanner 类负责对源代码进行标记。Parser 类使用 Scanner 类解析源文件。Semantics 类定义了每次应用产生式时要执行的语义操作。最后，Generator 类负责构建实际的可执行文件。Generator 使用 .NET 命名空间 System.Reflection.Emit 来生成 IL 代码。Ildasm 框架 SDK 工具可用于查看生成的可执行文件的内容。
剖析 Sharp 编译器架构
每个编译器至少包含三个部分：扫描器、解析器和代码生成器。
扫描器
与其余部分相比，扫描器执行的工作非常基础，但对于整体设计的简洁性至关重要。扫描器的任务是将源代码分解成标记。Sharp 语句 int [] array = new [size]; 将被扫描器分解为“int,[,],identifier,=,new,[,identifier,],;”。扫描器的代码可以通过多种方式编写，但最优雅的方式是基于某些工具生成的 DFA，在我们这里是 Gold Parser。使用这种方法可以使代码更加精简和优雅。以下 C# 方法负责从源文件中获取下一个标记。
public Token GetNextToken()
{
State currentState = m_Language.StartState;
State lastAcceptingState = null;
int tokenStart = m_Cursor + 1;
int tokenEnd = tokenStart;
int tokenStartColumn = m_Column;
int tokenStartLine = m_Line;
Token result = null;
//
// Retrieve one character at a time from the source input and walk through the DFA.
// when we enter an accepting state save it as the lastAcceptingState and keep walking.
// If we enter an error state (nextState == null) then return the lastAcceptingState, or
// a null token if the lastAcceptingState is never set.
//
while(true)
{
// Don't advance the cursor.
char nextChar = PeekNextChar();
// Return an EOF token.
if(nextChar == (char)0 && (lastAcceptingState == null))
{
result = new Token(m_Language.Symbols[0]);
result.Column = tokenStartColumn;
result.Line = tokenStartLine;
break;
}
// Get next state from current state on the next character.
State nextState = currentState.Move(nextChar);
// If the next state is not an error state move to the next state.
if(nextState != null)
{
// Save accepting state if its accepting.
if(nextState.IsAccepting)
{
lastAcceptingState = nextState;
tokenEnd = m_Cursor + 2;
}
// Move to the next state.
currentState = nextState;
// Advance cursor.
nextChar = GetNextChar();
}
else
{
// We have entered an error state. Thus either return the lastAcceptingState or
// a null token.
if(lastAcceptingState == null)
{
result = new Token(null);
result.Column = tokenStartColumn;
result.Line = tokenStartLine;
result.Text = new string(m_Buffer,tokenStart,tokenEnd - tokenStart);
}
else
{
result = new Token(lastAcceptingState.Accepts);
result.Column = tokenStartColumn;
result.Line = tokenStartLine;
result.Text = new string(m_Buffer,tokenStart,tokenEnd - tokenStart);
}
break;
}
}
return result;
}
解析器
解析器是整个编译器的核心。由于此解析器使用了 Gold Parser 生成的预计算表，因此剩余的任务是编写使用该表的算法。以下 C# 方法使用解析表来解析由扫描器构造的源文件标记。这是经典表驱动 LR 解析器的算法。
public Module CreateSyntaxTree()
{
// Are we currently in a comment block.
bool inCommentBlock = false;
// Parser stack.
Stack stack = new Stack();
// Syntax stack.
SyntaxStack syntaxStack = new SyntaxStack();
m_Scanner.Reset();
ParserState currentState = m_Language.ParserStartState;
// m_Language.ParserStartState is our parser start state.
// Push start state.
stack.Push(currentState);
while(true)
{
// Get next token.
Token nextToken = m_Scanner.PeekNextToken();
Symbol nextSymbol = nextToken.Symbol;
// Ignore whitespace.
if(nextSymbol.Type == SymbolType.Whitespace)
{
m_Scanner.GetNextToken();
continue;
}
// Ignore comment blocks
if(nextSymbol.Type == SymbolType.CommentStart)
{
m_Scanner.GetNextToken();
inCommentBlock = true;
continue;
}
// Ignore comment blocks
if(nextSymbol.Type == SymbolType.CommentEnd)
{
m_Scanner.GetNextToken();
inCommentBlock = false;
continue;
}
// Ignore stuff inside comments
if(inCommentBlock)
{
m_Scanner.GetNextToken();
continue;
}
// Print(stack); //Uncomment this to see the parse stack.
// PrintSyntax(syntaxStack.Stack); // Uncomment this to see the syntax stack.
// Lookup action out of current state.
Action action = currentState.Find(nextSymbol);
// Do we have a parser error ? (Entered an invalid state.)
if(action == null)
{
StringBuilder message = new StringBuilder("Token Unexpected, expecting [ ");
for(int x = 0; x < currentState.Actions.Length; x++)
{
if(currentState.Actions[x].Symbol.Type == SymbolType.Terminal)
message.Append(currentState.Actions[x].Symbol.Name + " ");
}
message.Append("]");
if(Error != null)
Error(nextToken,message.ToString());
return null;
}
// Should we shift token and the next state on the stack.
else if(action.Type == ActionType.Shift)
{
Token token = m_Scanner.GetNextToken();
stack.Push(token.Symbol);
syntaxStack.Push(token.Text);
stack.Push(action.ParserState);
}
// Should we reduce ?
else if(action.Type == ActionType.Reduce)
{
// Pop off the stack however many state-symbol pairs as the Production
// has Right Terminals,Nonterminals.
int rightItems = action.Production.Right.Length;
for(int i = 0;i < rightItems;i++)
{
stack.Pop();
stack.Pop();
}
// Find the top of the stack.
ParserState topState = (ParserState)stack.Peek();
// Push left hand side of the production.
stack.Push(action.Production.Left);
// Find next state by looking up the action for the top of the stack
// on the Left hand side symbol of the production.
stack.Push(topState.Find(action.Production.Left).ParserState);
// Apply semantic rule. Applies the semantic rule associated
// with the production used. This ultimately creates the
// syntax tree.
Semantics.Apply(action.Production,syntaxStack);
}
else if(action.Type == ActionType.Accept)
{
Debug.WriteLine("Accept");
return (Module)syntaxStack.Pop();
}
currentState = (ParserState)stack.Peek();
}
return null;
}
解析和语法栈
解析器使用一个解析栈来压入终结符和非终结符。一旦确定应该使用某个产生式，它就会弹出构成产生式右侧的顶部元素，并压入新的非终结符。如果在解析结束时，栈中只有一个非终结符，并且它本身就是起始非终结符，则解析成功。语法栈用于语义操作，这些操作赋予源代码真正的意义。以下列表是每个标记后解析栈和语法栈内容的打印输出。
源代码
module Test
{
int x;
void Foo(int x, int y)
{
return;
}
return;
}
语法和解析栈
Stack : 0
Syntax :
Stack : 0 module 1
Syntax : module
Stack : 0 module 1 identifier 2
Syntax : module Test
Stack : 0 module 1 identifier 2 { 3
Syntax : module Test {
Stack : 0 module 1 identifier 2 { 3 int 96
Syntax : module Test { int
Stack : 0 module 1 identifier 2 { 3 Primitive_Type 109
Syntax : module Test { Core.Type
Stack : 0 module 1 identifier 2 { 3 Type 157
Syntax : module Test { Core.Type
Stack : 0 module 1 identifier 2 { 3 Type 157 identifier 158
Syntax : module Test { Core.Type x
Stack : 0 module 1 identifier 2 { 3 Type 157 identifier 158 ; 117
Syntax : module Test { Core.Type x ;
Stack : 0 module 1 identifier 2 { 3 Variable_Declaration 173
Syntax : module Test { Core.Variable
Stack : 0 module 1 identifier 2 { 3 Statement 152
Syntax : module Test { Core.Variable
Stack : 0 module 1 identifier 2 { 3 Statements 153
Syntax : module Test { Core.StatementCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 void 107
Syntax : module Test { Core.StatementCollection void
Stack : 0 module 1 identifier 2 { 3 Statements 153 Primitive_Type 109
Syntax : module Test { Core.StatementCollection Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157
Syntax : module Test { Core.StatementCollection Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158
Syntax : module Test { Core.StatementCollection Core.Type Foo
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159
Syntax : module Test { Core.StatementCollection Core.Type Foo (
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 int 96
Syntax : module Test { Core.StatementCollection Core.Type Foo ( int
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Primitive_Type 109
Syntax : module Test { Core.StatementCollection Core.Type Foo ( Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Type 171
Syntax : module Test { Core.StatementCollection Core.Type Foo ( Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Type 171 identifier 172
Syntax : module Test { Core.StatementCollection Core.Type Foo ( Core.Type x
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameter 165
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.Parameter
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ,
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169 int 96
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection , int
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169 Primitive_Type 109
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection , Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169 Type 171
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection , Core.Type
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169 Type 171 identifier 172
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection , Core.Type y
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 , 169 Parameter 170
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection , Core.Parameter
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection )
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) {
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3 return 98
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) { return
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3 return 98 ; 99
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) { return ;
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3 Statement 152
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) { Core.Return
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3 Statements 153
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) { Core.StatementCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 { 3 Statements 153 } 154
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) { Core.StatementCollection }
Stack : 0 module 1 identifier 2 { 3 Statements 153 Type 157 identifier 158 ...
( 159 Parameters 166 ) 167 Body 168
Syntax : module Test { Core.StatementCollection Core.Type Foo ( ...
Core.ParameterCollection ) Core.Body
Stack : 0 module 1 identifier 2 { 3 Statements 153 Function_Declaration 150
Syntax : module Test { Core.StatementCollection Core.Function
Stack : 0 module 1 identifier 2 { 3 Statements 153 Statement 155
Syntax : module Test { Core.StatementCollection Core.Function
Stack : 0 module 1 identifier 2 { 3 Statements 153
Syntax : module Test { Core.StatementCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 return 98
Syntax : module Test { Core.StatementCollection return
Stack : 0 module 1 identifier 2 { 3 Statements 153 return 98 ; 99
Syntax : module Test { Core.StatementCollection return ;
Stack : 0 module 1 identifier 2 { 3 Statements 153 Statement 155
Syntax : module Test { Core.StatementCollection Core.Return
Stack : 0 module 1 identifier 2 { 3 Statements 153
Syntax : module Test { Core.StatementCollection
Stack : 0 module 1 identifier 2 { 3 Statements 153 } 154
Syntax : module Test { Core.StatementCollection }
Stack : 0 module 1 identifier 2 Body 183
Syntax : module Test Core.Body
Stack : 0 Module 184
Syntax : Core.Module
Accept
语法树和解析树的视觉表示
代码生成器
一旦我们有了语法树，代码生成就相当直接了。由于 MSIL 是一个基于栈的指令集，代码生成可以很容易地与之集成。用于从 Module 类发出 .NET 程序集的代码都位于 Generator.cs 源文件中。
Gold Parser - 语法源文件
以下文本文件是 Gold Parser 用来构建 DFA 和 LALR 状态表的源文件。它生成的已编译语法文件由 Language 类使用。
"Name" = Sharp Grammar
"Version" = 1.0
"Author" = Michael Bebenita
"Start Symbol" = <Module>
"Case Sensitive" = True
! Scanner Rules
{LETTER} = {Letter}
{DIGIT} = {Digit}
{ALPHA_NUMERIC} = {DIGIT} + {LETTER}
{HEX_DIGIT} = {DIGIT} + [a-fA-F]
{String Char} = {Printable} - ["]
! Identifiers must start with a letter followed any amount of letters, digits or underscores.
identifier = {LETTER}({ALPHA_NUMERIC} | _)*
! Literals may be either true or false, integers, real numbers, or characters.
boolean_literal = (true)|(false)
integer_literal = ({DIGIT}+) | (0x{HEX_DIGIT}+)
real_literal = {DIGIT}*.{DIGIT}+f
character_literal = ''{LETTER}''
string_literal = '"'{String Char}*'"'
<Literal> ::= boolean_literal
| integer_literal
| real_literal
| character_literal
| string_literal
!! Types
<Type> ::= <Structure_Type>
| <Primitive_Type>
| <Array_Type>
<Structure_Type> ::= identifier
<Primitive_Type> ::= bool
| int
| real
| char
| void
<Array_Type> ::= <Structure_Type> '[' ']'
| <Primitive_Type> '[' ']'
!!
!! Global stuff. Module and body declaration.
!!
<Module> ::= module identifier <Body>
<Body> ::= '{' <Statements> '}'
| '{' '}'
<Name> ::= identifier
| <Name> . identifier
!!
!! Variable stuff.
!!
<Variable_Declarations> ::= <Variable_Declaration>
| <Variable_Declarations> <Variable_Declaration>
<Variable_Declaration> ::= <Type> identifier ;
| <Type> identifier = <Expression> ;
| <Type> identifier = new '[' <Expression> ']' ;
| <Type> identifier = '{' <Elements> '}' ;
<Elements> ::= <Element>
| <Elements> , <Element>
<Element> ::= <Expression>
| '{' <Elements> '}'
!!
!! Function stuff.
!!
<Function_Declaration> ::= <Type> identifier '(' ')' <Body>
| <Type> identifier '(' <Parameters> ')' <Body>
<Parameters> ::= <Parameter>
| <Parameters> , <Parameter>
<Parameter> ::= <Type> identifier
| ref <Type> identifier
<Function_Call> ::= <Name> '(' ')'
| <Name> '(' <Arguments> ')'
<Arguments> ::= <Argument>
| <Arguments> , <Argument>
<Argument> ::= <Expression>
| ref <Expression>
!!
!! Structure stuff.
!!
<Structure_Declaration> ::= struct identifier '{' <Variable_Declarations> '}'
| struct identifier '{' '}'
!!
!! Statements
!!
<Statements> ::= <Statement>
| <Statements> <Statement>
<Statement> ::= <Variable_Declaration>
| <Function_Declaration>
| <Structure_Declaration>
| <Function_Call> ;
| <Assignment> ;
| return <Expression> ;
| return ;
| if '(' <Expression> ')' <Body>
| if '(' <Expression> ')' <Body> else <Body>
| while '(' <Expression> ')' <Body>
| do <Body> while '(' <Expression> ')'
| for '(' <Assignment> ; <Expression> ; <Assignment> ')' <Body>
!
! Expressions
!
<Assignment> ::= set <Name> = <Expression>
| set <Name> '[' <Expression> ']' = <Expression>
| set <Name> ++
| set <Name> --
<Expression> ::= <Expression_Term>
| <Expression> + <Expression_Term>
| <Expression> - <Expression_Term>
<Expression_Term> ::= <Expression_Factor>
| <Expression_Term> * <Expression_Factor>
| <Expression_Term> / <Expression_Factor>
<Expression_Factor> ::= <Expression_Binary>
| <Expression_Factor> % <Expression_Binary>
| <Expression_Factor> '>' <Expression_Binary>
| <Expression_Factor> '<' <Expression_Binary>
| <Expression_Factor> '>=' <Expression_Binary>
| <Expression_Factor> '<=' <Expression_Binary>
| <Expression_Factor> '==' <Expression_Binary>
| <Expression_Factor> '!=' <Expression_Binary>
<Expression_Binary> ::= <Expression_Unary>
| <Expression_Binary> && <Expression_Unary>
| <Expression_Binary> || <Expression_Unary>
<Expression_Unary> ::= + <Expression_Primary>
| - <Expression_Primary>
| ! <Expression_Primary>
| <Expression_Primary>
| <Expression_Primary> '[' <Expression> ']'
<Expression_Primary> ::= <Name>
| <Function_Call>
| <Literal>
| '(' <Expression> ')'