程序的语法

语法

计算机语言同样也是一种语言，是一种计算机能够理解的语言，我们想要和计算机对话，就要去学习这种语言。和我们人类的语言一样，计算机语言也是有语法的。以汉语为例，我说『我是中国人』，因为汉语的语法，你听到这句话之后会知道『我』是主语，『是』是谓语，『中国人』是宾语，同时你又很清楚每一个成分的含义，最终理解了整句话的意思。

同样，对于计算机语言也是一样，有着程序的语法，一个解释器知道哪个词是操作数，哪个是操作符，哪个是关键字，它们都有着怎样的含义和功能，通过解释器的解释，计算机明白了某行语句的意义，然后进行运算，得到最后的执行结果。

语法图

语法图就是用来表示一种编程语言语法规则设计的示意图，它很直观的显示出了在一种编程语言中，允许使用的语句和不支持的语句。语法图十分易于阅读：只需跟随箭头指示的路径。一些路径表示选择。另一些路径表示循环。

一个简单的语法图

这里我们举一个语法图的例子：

这个语法图就是一个描述了简单的加减运算的语法图，term 在其中的意思就是一个操作数，一开始输入一个操作数，有三条路径可以选择『+』，『-』和退出，如果进入了『+』、『-』路径，则需要再输入一个操作数，之后的路径包括『+』、『-』和退出，如此循环，就能解释一个简单的加减法解释器。

根据上边的语法图，下面的表达式都是合法的：

• 4
• 1 + 1
• 1 + 4 - 3

下面的表达式不合法：

• -
• + -
• 2 +
• + 3 - 3

语法图可以帮助我们：

• 用图的方式表示出一种计算机语言的设计规范
• 可以帮助理解解释器，将图表表示成代码

代码实现（Python）

学习一样东西最简单的就是阅读代码（Read the Fucking Code！），因此我们先来看完整代码然后再来分析一下，完整代码在： https://github.com/luoyhang003/Pascal-Interpreter/blob/master/calc3.py

# Token Types:  # EOF: End-Of-File    INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'    class Token(object):      def __init__(self, type, value):          # Token types: INTEGER, PLUS, MINUS, EOF          self.type = type          # Token value: 0,1,2,3,4,5,6,7,8,9,+,None          self.value = value        def __str__(self):          """ The format of the print infomation For examle: Token(INTEGER, 3) Token(PLUS, '+') Token(MINUS, '-') """          return 'Token({type},{value})'.format(                  type = self.type,                  value = repr(self.value)                  )        def __repr__(self):          return self.__str__()    class Interpreter(object):      def __init__(self, text):          # Process the whole input          # e.g. 3+5          self.text = text          self.pos = 0          self.current_token = None          self.current_char = self.text[self.pos]        def error(self):          raise Exception('Error Parsing Error!')        def advance(self):          # Advance the pos and set current_char          self.pos += 1            if self.pos > len(self.text)-1:              self.current_char = None          else:              self.current_char = self.text[self.pos]        def skip_whitespace(self):          # Skip space          while self.current_char is not None and self.current_char.isspace():              self.advance()        def integer(self):          # Support mutidigit integer          result = ''            while self.current_char is not None and self.current_char.isdigit():              result += self.current_char              self.advance()            return int(result)        def get_next_token(self):          """ Lexical Analyzer: Parsing the input into tokens. Strategy: 1. is pos past the end of the text? 2. if so, return EOF 3. get a character at pos, and decide its type depends on the single char 4. if it is a space, advance the pos 5. if it is a digit, then convert it to integer and return INTEGER token 6. if it is a '+', then return PLUS token 7. if it is a '-', then return MINUS token """            while self.current_char is not None:                if self.pos > len(self.text) - 1:                  return Token(EOF, None)                current_char = self.text[self.pos]                if current_char.isspace():                  self.skip_whitespace()                  continue                if current_char.isdigit():                  return Token(INTEGER, self.integer())                if current_char == '+':                  self.advance()                  return Token(PLUS, '+')                if current_char == '-':                  self.advance()                  return Token(MINUS, '-')                  self.error()            return Token(EOF, None)        def eat(self, token_type):          # compare the current token with the passed token type          # if they match then eat the current token and assign next token to the self.current_token          # otherwise raise an Exception            if self.current_token.type == token_type:              self.current_token = self.get_next_token()          else:              self.error()        def term(self):          # return an Integer Token's value          token = self.current_token          self.eat(INTEGER)          return token.value                def expr(self):          # expr -> INTEGER PLUS INTEGER          # expr -> INTEGER MINUS INTEGER            self.current_token = self.get_next_token()            result = self.term()            while self.current_token.type in (PLUS, MINUS):              token = self.current_token              if token.type == PLUS:                  self.eat(PLUS)                  result += self.term()              if token.type == MINUS:                  self.eat(MINUS)                  result -= self.term()            return result    def main():      while True:          try:              text = raw_input('cal> ')          except EOFError:              break          if not text:              continue            interpreter = Interpreter(text)          result = interpreter.expr()          print(result)    if __name__ == '__main__':      main()

在代码中，我们首先定义了四种 Token：整数（Integer）、加法（+）、减法（-）、终止符（EOF）

代码中主要分为几个主要部分：

• term 方法，在表达式中解析出一个整数

    def term(self):          # return an Integer Token's value          token = self.current_token          self.eat(INTEGER)          return token.value

• expr 方法，根据语法图的流程来解析语句

    def expr(self):          # expr -> INTEGER PLUS INTEGER          # expr -> INTEGER MINUS INTEGER            self.current_token = self.get_next_token()            result = self.term()            while self.current_token.type in (PLUS, MINUS):              token = self.current_token              if token.type == PLUS:                  self.eat(PLUS)                  result += self.term()              if token.type == MINUS:                  self.eat(MINUS)                  result -= self.term()            return result

expr 方法，首先调用 term 方法获取一个整数，然后判断后边的 Token 是加法还是减法，之后再获取一个整数，然后进行运算，然后判断之后还有没有运算符，如果没有就返回结果，如果还有就重复以上步骤。我们看到 expr 方法是严格按照语法图进行解释的。

执行结果

cal> 1+2  3  cal> 1+4-3  2  cal> 1+ 5 -6  0  cal> 1 +  Traceback (most recent call last):    File "calc3.py", line 176, in <module>      main()    File "calc3.py", line 172, in main      result = interpreter.expr()    File "calc3.py", line 155, in expr      result += self.term()    File "calc3.py", line 136, in term      self.eat(INTEGER)    File "calc3.py", line 131, in eat      self.error()    File "calc3.py", line 54, in error      raise Exception('Error Parsing Error!')  Exception: Error Parsing Error!

文法

文法是另一种被广泛使用的、用于指定一种程序设计语言语法的表示法，它叫做『上下文无关文法』，简称文法。

为什么要使用文法？

• 文法以更简明的方式说明一种程序设计语言的语法。比起来语法图，文法十分简洁。
• 文法可以用作很好的文档
• 文法可以非常方便的转换成代码（非常方便~）

文法原理

我们以『3 * 4 / 5 * 2』这样的算数乘除表达式为例，它对应的文法表达式为：

expr: factor ((MUL | DIV) factor)*

factor: INTEGER

一段文法由 一系列的规则（rule） 组成，在上述文法中，我们有两条规则： expr: factor ((MUL | DIV) factor)* 和 factor: INTEGER

一条规则由由 一个非终结符（称规则的头或者左边） 、 一个冒号： 、 一系列终结符非终结符（称规则的主体或者右边） 组成

分析以上文法：

• expr 、 factor 这样的变量叫做非终结符
• MUL 、 DIV 、 Integer 这样的标记称为终结符
• | 表示『或』，多选一。 (MUL | DIV) 表示要么 MUL（乘）要么 DIV（除）
• ( ) 一对圆括号表示把终结符非终结符组合起来，就像 (MUL | DIV) 一样
• ( )* 表示匹配组合里面的内容 0 次或者多次，就像 while 循环

现在我们以解释『3 * 4 / 5 * 2』这样的算数乘除表达式为例：

expr  factor ((MUL | DIV) factor)*  factor MUL factor ((MUL | DIV) factor)*  factor MUL factor DIV factor ((MUL | DIV) factor)*  factor MUL factor DIV factor MUL factor  INTEGER MUL INTEGER DIV INTEGER MUL INTEGER   3       *   4       /   5       *   2

将文法映射称为为代码

• 对于文法中定义的每一条规则 R，都可以在代码中变成同名的方法 R()
• 对于多个可选项 ( | ) 可以编程为 if-else 语句
• 可选的 ( )* 集合编程称为 while 语句，表示可以循环 0~n 次

因此，上述文法用代码表示出来就是：

• factor 方法

def factor(self):      # return an Integer Token's value      # factor: Integer      token = self.current_token      self.eat(INTEGER)      return token.value

• expr 方法

def expr(self):      # Arithmetic expression parser      # expr: factor( (MUL | DIV) factor)*      # factor: Integer        result = self.factor()        while self.current_token.type in (MUL, DIV):          token = self.current_token            if token.type == MUL:              self.eat(MUL)              result = result * self.factor()          elif token.type == DIV:              self.eat(DIV)              result = result / self.factor()        return result

扩充我们的文法

加入加减运算

因为，我们加入了加减运算，因此现在存在运算优先级问题，很显然乘除运算优先级要高于加减运算

我们得到以下的优先级表格：

操作符	优先级	结合性
-	2	左结合
/	1	左结合

根据优先级表格构建文法：

• 为每个优先级定义一个非终结符。非终结符所在产生式的主体应该包含同等级的算术运算符和优先级高一级的非终结符
• 为表达式创建一个额外的非终结符 factor 作为基本单位，在我们的例子中该基本单位是整数。通用的规则是如果你有 N 层优先级，那么你总共需要 N + 1 个非终结符：每层优先级需要一个非终结符，加上一个用作表达式基本单位的非终结符。

更新我们的文法：

expr: term ((PLUS | MINUS) term)*

term: factor ((MUL | DIV) factor)*

factor: INTEGER

加入括号表达式

在之前，我们的基本单位只有 INTEGER，这次我们加入括号表达式。

更新后的文法为：

expr: term ((PLUS | MINUS) term)*

term: factor ((MUL | DIV) factor)*

factor: INTEGER | LPAREN expr RPAREN

• LPAREN 表示左括号，RPAREN 表示右括号
• 括号表达式内的非终结符 expr 表示 expr 规则

下面我们以『 3 * （1 + 5）』为例，来说明该文法是如何工作的：

最终的四则运算解释器

• 完整代码见： https://github.com/luoyhang003/Pascal-Interpreter/blob/master/calc6.py

# Token Types:  # EOF: End-Of-File  INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (      'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'  )  class Token(object):      def __init__(self, type, value):          # Token types: INTEGER, PLUS, MINUS, MUL, DIV, EOF          self.type = type          # Token value: 0,1,2,3,4,5,6,7,8,9,,+,-,*,/,None          self.value = value        def __str__(self):          """ The format of the print infomation For examle: Token(INTEGER, 3) Token(PLUS, '+') Token(MINUS, '-') TOKEN(MUL, '*') TOEKN(LPAREN, ')') """          return 'Token({type},{value})'.format(                  type = self.type,                  value = repr(self.value)                  )        def __repr__(self):          return self.__str__()    class Lexer(object):      def __init__(self, text):          # Process the whole input          # e.g. 3+ 5 * 2 - 4/2          self.text = text          self.pos = 0          self.current_char = self.text[self.pos]        def error(self):          raise Exception('Invalid character!')        def advance(self):          # Advance the pos and set current_char          self.pos += 1            if self.pos > len(self.text)-1:              self.current_char = None          else:              self.current_char = self.text[self.pos]        def skip_whitespace(self):          # Skip space          while self.current_char is not None and self.current_char.isspace():              self.advance()        def integer(self):          # Support mutidigit integer          result = ''            while self.current_char is not None and self.current_char.isdigit():              result += self.current_char              self.advance()            return int(result)        def get_next_token(self):          """ Lexical Analyzer: Parsing the input into tokens. Strategy: 1. dictate current char 2. if it is a space, advance the pos 3. if it is a digit, then convert it to integer and return INTEGER token 4. if it is a '+', then return PLUS token 5. if it is a '-', then return MINUS token 6. if it is a '*', then return MUL token 7. if it is a '/', then return DIV token 8. if it is a '(', then return LPAREN token 9. if it is a ')', then return RPAREN token """            while self.current_char is not None:                if self.current_char.isspace():                  self.skip_whitespace()                  continue                if self.current_char.isdigit():                  return Token(INTEGER, self.integer())                if self.current_char == '+':                  self.advance()                  return Token(PLUS, '+')                if self.current_char == '-':                  self.advance()                  return Token(MINUS, '-')                if self.current_char == '*':                  self.advance()                  return Token(MUL, '*')                if self.current_char == '/':                  self.advance()                  return Token(DIV, '/')                if self.current_char == '(':                  self.advance()                  return Token(LPAREN, '(')                if self.current_char == ')':                  self.advance()                  return Token(RPAREN, ')')                self.error()            return Token(EOF, None)    class Interpreter(object):      def __init__(self, lexer):          self.lexer = lexer          self.current_token = self.lexer.get_next_token()        def error(self):          raise Exception('Invalid Syntax')        def eat(self, token_type):          # compare the current token with the passed token type          # if they match then eat the current token and assign next token to the self.current_token          # otherwise raise an Exception            if self.current_token.type == token_type:              self.current_token = self.lexer.get_next_token()          else:              self.error()        def factor(self):          # factor: Integer | LPAREN expr RPAREN          token = self.current_token            if token.type == INTEGER:              self.eat(INTEGER)              return token.value            if token.type == LPAREN:              self.eat(LPAREN)              result = self.expr()              self.eat(RPAREN)              return result        def term(self):          # term: factor( (MUL | DIV) factor)*          # factor: Integer          result = self.factor()            while self.current_token.type in (MUL, DIV):              token = self.current_token                if token.type == MUL:                  self.eat(MUL)                  result = result * self.factor()              elif token.type == DIV:                  self.eat(DIV)                  result = result / self.factor()            return result        def expr(self):          # expr: term( (PLUS | MINUS) term)*          # term: factor( (MUL | DIV) factor)*          # factor: Integer          result = self.term()            while self.current_token.type in (PLUS, MINUS):              token = self.current_token                if token.type == PLUS:                  self.eat(PLUS)                  result = result + self.term()              elif token.type == MINUS:                  self.eat(MINUS)                  result = result - self.term()            return result    def main():      while True:          try:              text = raw_input('cal> ')          except EOFError:              break          if not text:              continue            lexer = Lexer(text)          interpreter = Interpreter(lexer)          result = interpreter.expr()          print(result)    if __name__ == '__main__':      main()

运行结果

cal> 1+1  2  cal> 1*3  3  cal> 1+3*3  10  cal> 5*(1+5)  30  cal> (5+6)/(3-1)*2  10

参考资料

• Python Cookbook(第3版)

• Ruslan’s Blog

</div>

来自： http://blog.csdn.net/luoyhang003/article/details/50532770