Shyaru I

诸位新年好,这里是一如既往的AS。

时值新春,应该大家都在享受假期吧?

恩,情人节是否和中意的人有了新进展呢?

除夕有没有和全家人开心吃年夜饭呢?

接下来的假期,也请尽情享受才好。

言归正传。

这一篇讨论的对象是Shyaru,这个项目打算是完成一个解释器,用于服务后面更远的一个项目。不过工作之后时间并不多,AS的兴趣又很杂,直接导致了进度缓慢。还是放假这几天努力填坑,大致完成了文法分析部分。

不过,前端这部分我还留有疑问,未来几天还需要探索一阵。不出意外我应该会另开一个分支来对照。

应该会有很多不科学的地方,这部分做后端的时候是会矫正的。

语法大致是类javascript,虽然我最开始很想做一个python的子集,但是使用缩进控制层次做起来还是太难,所以放弃了。

请注意,只是语法“像”js。事实上,js的很多语言特性现在没办法实现,换言之,只是个空架子而已。

主要参考文档包括: Simple Top-Down Parsing in Python, Top Down Operator Precedence,对于表达式的解析使用Vaughan Pratt提出的方法。

Shyaru目前是一个LL(1)的parser,主要作用是把每一个以;结尾的逻辑行,处理成为一颗抽象语法树(AST)。

如果输入是合法的源文件的话,输出是一个以AST为元素的列表。

Shyaru有一些基本的对语法正确性的判断,但是Shyaru不会处理,而且直接报错退出 —- 23333。

Shyaru目前对错误的诊断没有精确到行,所以如果报错的话: Good Luck。

OK,开始吧。

文法分析都应该从产生式开始?虽然您读到后面大概会发现,产生式并不是特别需要在意的内容。原因是我们可以很容易地解析出来表达式,所以产生式的关注点就只是在语句上。

program -> statements
statements -> statement | statements
statement -> block | if-statement | while-statement | assign-statement | function-definition-statement | expr + ';'
block -> '{' + statements + '}'
if-statement -> 'if' + '(' + expr + ')' + block {'else' + block}
while-statement -> 'while' + '(' + expr + ')' + block
assign-statement -> 'var' + expr

上面是目前使用的产生式。可以注意到,expr这个非终结字符我没有去推导,事实上,我是希望您最好把这玩意看作是终结字符。然后,和一般自顶而下推导不同,expr下的优先级是没有进行指定的 —- 但是不代表没有优先级。Vaughan Pratt法可以通过引入一个叫做bp(bind power)的值,很舒服地去解决表达式中优先级的问题,而不需要在产生式中去多引入额外的非终结字符。如果您看过C programming language后面附录中的产生式,或者您写过任何一个自顶而下的文法产生式,大概您就会知道,这个过程确实不是那么友好。

Vaughan Pratt法主要用于表达式的解析,所以从表达式解析开始。

V.P法核心在于这个函数:

def expression(rbp=0):
    global token
    t = token
    token = next()
    left = t.nud()
    while rbp < token.lbp:
        t = token
        token = next()
        left = t.led(left)
    return left

更详细的解释请翻看参考文档2,这里我只说自己的理解。

V.P把一个表达式中的token分为两种,一种有nud,另一种有led,这两种token交叉存在。有led的token,我们认为它是某一个运算符,而,有nud的token,我们认为它是一个字面量。

另一种方式帮助理解就是,试想一棵二叉树,那么,有led的token,我们认为是一个父节点,而nud的token,是其叶子节点。

举个栗子。2 + 3的话,2和3这两个token就是有nud的token。+就是有led的token。

nud全称是null denotation, led是left denotation, 上面还有一个lbp,这东西叫做left binding power。后面我们可以看到,lbp决定了优先级。

nud其实是字面值,我们总是从一个token的字面值开始的,比如 2+3。这个字面值会变成+的左叶子节点,右叶子节点由led求值出来。恩,好像不容易理解?多看就知道啦,很简单的。

有一个问题是,是的,上面的token交叉存在的准则在 2+3这样简单的表达式中成立,但是如果是 2+-3呢?

其实,只要把-3看作另一个表达式,先求值就好。

token是LL(1)中的那个1,通过peek来决定后面的逻辑。next是一个全局的函数,它总能产生下一个token。

下面请您稍微翻翻参考文档2,这样大概会为下面的内容做一些准备,具体的,请看完Streamlining Token Class Generation 之前的部分。这部分您会知道一些譬如解析出一个最基本的计算表达式,以及通过lbp来控制优先级,请好好思考为什么能做到呢。

关于词法分析这方面,虽然我有打算自己写过(实际上也写了2333,在old里面),但是后来发现写词法分析器不是很明智的决定。就技术而已,词法分析器也只是正则的匹配而已,但是要保证正确性和完全性,实际上难度相当大,所以我还是用了tokenize这个库。不过这个库我觉得使用起来比较奇怪,推荐先看看文档。

另外,如果您从这里对照着看的话,我对于environment(对应参考文档的symbol_table)的处理和参考文档也不一样,这其实就是我的第一个疑问:作用域或者说上下文环境,应该暴露在文法分析这一步么?参考文档的作者没有在文法分析中设置上下文作用域,而是一个全局的作用域。我猜想后面作用域部分是交给后端来实现的。但是我觉得这部分,既然我能在文法分析的时候确定上下文,为何不在这里做上下文约束呢。

所以对应的,我的environment是一个类,而不是闭包。原因是我需要提供fork_env这个方法用于派生一个新的作用域,相对来说用闭包的话,这个方法就不是那么容易处理 —- 尽管我能通过消息传递的方式模拟闭包成为一个类,但是终究不是很符合习惯的行为。

这里还有一个疑问二:把所有的定义都放在一个字典中是好的么?或者,我应该用两个字典,一个放保留值另一个放定义值。保留值是指,比如if, while, for这样的关键字;{,},:这样的符号;以及None,True,False这样的常量。定义值是指,我定义的变量名,函数名,使用到的数字,出现的字符串等。

我是觉得分开逻辑上会清晰一点,事实上下午我也做了这样的尝试。不过,随之带来的问题就是复杂度提升了,因为涉及的字典变多了。

总而言之,这是environment这个类的一些情况。

class environment(object):
    def __init__(self, parent=None):
        self.env = dict()
        self.parent = parent
        self.child = None

    def __call__(self, identify, bp=0, auto_commit = True, search = True):
        s = self.env.get(identify)
        if not s:
            if search:
                s = self._search_identify(identify)
            if not s:
                class s(Token):
                    pass
                if auto_commit:
                    s.__name__ = 'symbol-{}'.format(identify)
                    s.id = identify
                    s.lbp = bp
                    self.env[identify] = s
                else:
                    s = None
            else:
                s.lbp = max(s.lbp, bp)
        else:
            s.lbp = max(s.lbp, bp)
        return s

    def _search_identify(self, identify):
        if not self.parent:
            return None
        else:
            parent = self.parent
            value = parent.env.get(identify)
            if value:
                return value
            else:
                return parent._search_identify(identify)

    def fork_env(self):
        _new_env = type(self)(self)
        self.child = _new_env
        return _new_env

为了更符合某些习惯,搜寻变量名的时候如果当前作用域没找到会往上搜寻,直到最顶层的全局作用域。

不过,实际上,如果您认真看过代码,会发现并不是那么美好。

参考资料的实现中,当然作为借鉴者,我也是这样做的,这个变量表实际上作为索引的是变量的type(比如'(name)', '(number)'),而不是真正的值(比如 'a')。就我个人而言,更喜欢的是用值来作为索引,或者是类型+值的形式。这部分我大概会在随后进行尝试。因为我不觉得这是个坏主意。

__call__方法中,search变量控制搜索变量要不要去父环境搜索,用处是希望在本环境中初始化一个和父环境同名的变量的时候。另外的auto_commit是用来保证查找变量的时候,不过因为找不到该变量而新建一个。这个在常量部分是有用处的。

另外有一个技巧吧,就是这个:

s = dict()
this['scope'] = environment()

这个其实很有用啦,主要是装饰器里面会很方便。

比如这个:

def method(identify):
    scope = this['scope']
    s = scope(identify)
    assert issubclass(s, Token)
    def bind(func):
        setattr(s, func.__name__, func)
    return bind

装饰器中只能这样才能动态变化scope哦?原因是dict变量访问使得变量的赋值被延迟了,而不是最开始就被决定。这玩意是我工作的时候某天发现的……

常量部分其实处理起来意外麻烦,主要是展示问题。比如我希望 a = None 展示成为 ( (op =) (name a) (None)),但是None会被解析成为一个name,所以不能走一般的name流程啦……这部分处理和参考资料上处理并不一样就是了。

如果看完了表达式解析部分的话,就轮到语句部分解析了。

vp最开始设计的时候,设计出来的语言是门函数式编程语言,参考资料2也是如此。但是个人还是希望引入语句的。

根据产生式,把parser写成这样;

def parser(program):
    global token, next
    next = _tokenize(program).next
    token = next()
    r_list = statements()
    return r_list

statements的结束可能有两种情况,一种是源代码结束,另一种是块结束。不过,嘛,statements并没有什么技巧性的东西,所以看看代码就好。

需要着重说的是statement。

def statement():
    global token
    t = token
    if getattr(t, 'std', None):
        advance()
        return t.std()
    if token.id != ';':
        v = expression(0)
    else:
        v = None
    advance(';')
    return v

产生式上已经说明白了,有可能是var赋值语句,if语句,while语句,function语句或者干脆就是表达式+;。

最后一种情况不太需要特殊处理,只需要正常express()一次就能得到ast,至于最后的;吃掉就好。

但是前面几种语句都是需要特殊处理的。

参考文档1中提出了引入std()方法。于是这样考虑,如果语句以有std的token开始,那么就特殊处理。std其实写起来意外简单……恩。诸如复杂的大概也只有function定义了。

function定义语句稍微比较复杂一点,因为要考虑参数,比如无参或者多参的情况。另外比如if,while或者function都是有自己的作用域的,所以每一次分配独立的作用域比较好,我是这么想的。

@method('function')
def std(self):
    t = token
    if t.id != '(name)':
        raise Exception('Error function name')
    scope = this['scope'].fork_env()
    args_list = []
    advance()
    advance('(')
    while True:
        if token.id == ')':
            break
        if token.id != '(name)':
            raise SyntaxError('Excepted args name')
        args_list.append(token)
        symbol = scope('(name)', search=False)
        s = symbol()
        s.value = token.value
        advance()
        if token.id == ',':
            advance()
    advance(')')
    self.left = t
    self.right = args_list
    self.extra = block()
    return self

另外说一句,我没有写for语句也是因为比较麻烦,我不是特别想好应该怎么处理for语句生成的ast这样。

说起函数定义,另外说说函数调用。其实函数调用只需要把'('看成一个运算符就可以了。不过这样有另一个问题,就是如果有类加入,会不能区分类调用和函数调用,所以老实说我也比较踟蹰。

恩,大致如此,虽然我说的很不详细吧……

建议阅读上文提到的参考资料以及我这里的修改,有兴趣的话也可以稍微阅读对照一下Shyaru的代码,我觉得还是很有意思的,特别是使用装饰器防止重复代码那部分,个人觉得实现很漂亮,不过导致了难以阅读也是问题。

代码里面老实说有不少patch,比如

elif token_type == tokenize.NEWLINE or token_type == 54:
   continue

这些都是用调试器调出来的,比如那个54那个type,我一直觉得很神奇,因为我看了python token那部分的源代码,没发现54这个类型。尤其是,这玩意其实就是 tokenize.NEWLINE,也就是'\n',不过为什么不一样我还是不太明白。

就此搁笔。

感谢您的阅读。

新春快乐,鞠躬。

谢谢。

以上。