1.介绍

本系列文章参照该教程学习总结,欢迎查看原文。我个人的学习代码已经放到我的github
词法分析、语法分析、语义分析等定义请参考编译器解释器中的词法分析、语法分析、语义分析

英文原作者所有源代码查看

2. 文法

2.1 上下文相关和上下文无关

在本节中作者提了文法相关的内容。这里的文法均指的是上下文无关文法。上下文相关可以用两个句子对比来理解：

本来我是来得及看电影的，被你浪费了这么多时间去不了啦

2.我有一本来自国外的书

以上两个句子都有本来这个词，但是显然这个是上下文有关的，在不同的上下文中有不同的含义

2.1 文法的用处

文法以简明的方式说明一种程序设计语言的语法。不像语法图，文法十分简洁
文法可以用作很好的文档。
通常，你可以通过遵循一系列简单的规则将文法转换成代码。
有一组工具叫做解析器生成器，它接收一段文法作为输入，并且根据那段文法自动地生成一个解析器。

2.2 文法的原理

7 * 4 / 2 * 3

上式用文法来表示为：

一段文法由一系列规则（rule）组成，也称为产生式（productions）。在我们的文法中有两条规则：

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

上面介绍的文法中，像 MUL、DIV 和 INTEGER 这样的标记称为终结符（terminals），像 expr 和 factor 这样的变量称为非终结符（non-terminals）。非终结符通常由一系列终结符（和 | 或者）非终结符组成：
你可以这样读 expr 规则：“expr 可以是一个 factor 可选地接着一个乘法或者除法运算符，再接着另一个 factor，依次可选地接着一个乘法或者除法运算符，再接着另一个 factor……”

factor 是什么？就本文而言，factor 就是一个整数。

让我们快速地回顾一下文法中用到的符号和它们的含义（和正则表达式有限像）。

| – 多选一。表示“或”。所以 (MUL | DIV) 表示要么是 MUL，要么是 DIV。
( … ) – 一对圆括号表示把终结符（和 | 或者）非终结符组合起来，就像 (MUL | DIV) 一样。
( … )* – 匹配组合里面的内容 0 次或者多次。

如果你以前了解过正则表达式，那么 |、() 和 (…)* 这些符号对于你来说应该会比较熟悉。

一段文法通过说明它可以组成什么句子来定义一种语言（language）。这是如何使用文法推导出算术表达式：首先以开始符号 expr 开始，然后反复地用一个非终结符所在规则的主体替代该非终结符，直到产生一个只包含终结符的句子。那些句子组成了由文法定义的语言。

如果文法不能得到一条确定的算术表达式，那么它不支持该表达式，并且当解析器尝试识别该表达式时，解析器会生成一个语法错误。

我依次想了几个例子。下面是文法如何得到表达式 3 的例子（只接受一个3也是符合文法的，毕竟后面的*表示可以出现0次）：

这是文法如何得到表达式 3 * 7 的例子：

这是文法如何得到表达式 3 * 7 / 2 的例子：

2.3 文法转化成源代码

4个转化的准则如下:

文法中定义的每条规则，R，会变成一个同名的方法，而对那条规则的引用变成一个方法调用：R()。方法的主体跟着同一套准则的规则的主体流。
多个可选项 (a1 | a2 | aN) 变成 if-elif-else 语句。
可选的 (…)* 集合变成 while 语句，该语句可以循环 0 次或者多次。
每个符号引用 T 变成对 eat 方法的调用：eat(T)。eat 方法的工作方式是如果该方法匹配当前的 lookahead 符号，那么 eat 方法会传入符号 T，然后它会从词法分析器中得到一个新的符号，并且把该符号分配给内部变量 current_token。

直观图如下：

def factor(self):
    self.eat(INTEGER)

在我们的文法中有两条规则：expr 规则和 factor 规则。我们以 factor 规则（产生式）开始。根据准则，你需要创建一个名为 factor 的方法（准则 1），该方法有一个对以 INTEGER 符号为参数的 eat 方法的调用（准则 4）：
expr 规则变成 expr 方法（再次依据准则 1）。该规则开始是对变成了 factor() 方法调用的 factor 的引用。可选的集合 (…)* 变成一个 while 循环，(MUL | DIV) 变成 if-elif-else 语句。把那些代码段组合在一起，我们得到了下面的 expr 方法：

def expr(self):
    self.factor()
 
    while self.current_token.type in (MUL, DIV):
        token = self.current_token
        if token.type == MUL:
            self.eat(MUL)
            self.factor()
        elif token.type == DIV:
            self.eat(DIV)
            self.factor()

2.4 计算器

代码calc6.py是一个计算器（作者给的），可以处理包含整数和任意数量的乘法和除法（整除）运算符的有效算术表达式。与前面有所不同的是作者将词法分析器单独重构为一个Lexer类了

calc6.py

'''计算乘除法的计算器'''
INTEGER, MUL, DIV, EOF = 'INTEGER', 'MUL', 'DIV', 'EOF'


class Token(object):

    def __init__(self, type, value):
        self.type = type
        self.value = value

    def __str__(self):
        return 'Token({type},{value})'.format(
            type=self.type,
            value=repr(self.value)
        )

    def __repr__(self):
        return self.__str__()


class Lexer(object):

    '''词法分析器(Scanner)'''

    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Invalid syntax')

    def advance(self):
        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):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):
        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):
        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(MUL, '*')

            if self.current_char == '/':
                self.advance()
                return Token(DIV, '/')

            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):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        token = self.current_token
        self.eat(INTEGER)
        return token.value

    def expr(self):
        result = self.factor()
        while self.current_token.type in (MUL, DIV):
            token = self.current_token
            if token.type == MUL:
                self.eat(MUL)
                result *= self.factor()
            elif token.type == DIV:
                self.eat(DIV)
                result += self.factor()

        return result


def main():
    while True:
        try:
            text = input('calc>')
        except EOFError:
            break
        if not text:
            continue
        lexer = Lexer(text)
        interpreter = Interpreter(lexer)
        result = interpreter.expr()
        print(result)

if __name__ == '__main__':
    main()

3.概念复习

3.1 小练习

图片如下：

什么是上下文无关文法？

答：更多介绍请看《计算理论基础》第三章上下文无关文法，用自己简单来说就是这种上下文无关文法中利用规则对符号替换没有其他上下文的条件限制。（上下文就是要被替换的符号边上的其他符号）

文法有多少条规则或者产生式？

在本例子中是2个规则（也就是产生式），对应图上的两行内容

什么是终结符？（在图片中找到所有的终结符）

除了expr和factor以外的符号都是终结符

什么是非终结符？（在图片中找到所有的非终结符）

expr和 factor是终结符，可以被其他符号替换。替换非终结符直到只包含终结符的过程叫做推导，推导的结果组成了由文法定义的语言
5.什么是一条规则的头部？（在图片中找到所有的头部或者左边）
图中冒号左边的内容
6.什么是一条规则的主体？（在图片中找到所有的主体或者右边）
同种冒号的右边

文法的开始符号是什么？

第一条规则左边的非终结符符号称为开始符号

3.2 概念升华

上下文无关文法是计算机中非常常见的，书上定义如下

一个根据文法推导出符合文法的语言的例子

有6条规则R1到R6，文法定义如下，V表示所有用到的字符，E这里表示开始符号（非终结符）

正则语言是上下文无关的,这个是可以证明的

4. 作业

最后作者要求写一个能计算3+5*6这种表达式的计算器。一点提示没的话稍微有点困难，简单瞄了下后面一张，发现有这么一个文法的图，根据改图自己尝试修改calc6.py来支持这种优先级吧。

因为这节中原本中有些话用自己的话来组织语言可能描述不清楚，直接引用了一部分翻译的内容
参考资料：http://blog.jobbole.com/94326/

Blog of Kami Wan

No one is always busy. It just depends on what number you are on their priority list

实现pascal解释器(4)