Какой самый короткий способ написать парсер для моего языка? - PullRequest
Новая
       45

Какой самый короткий способ написать парсер для моего языка?

8 голосов
/ 04 октября 2009

PS. Где почитать про теорию разбора?

Ответы [ 11 ]

0 голосов
/ 07 декабря 2018

Если вас устраивает синтаксический анализ выражений , написание собственных анализаторов может быть невероятно коротким. Вот простой парсер Packrat, который принимает разумное подмножество PEG: 

import functools

class peg_parse:
    def __init__(self, grammar):
        self.grammar = {k:[tuple(l) for l in rules] for k,rules in grammar.items()}

    @functools.lru_cache(maxsize=None)
    def unify_key(self, key, text, at=0):
        if key not in self.grammar:
            return (at + len(key), (key, [])) if text[at:].startswith(key) \
                else (at, None)
        rules = self.grammar[key]
        for rule in rules:
            l, res = self.unify_rule(rule, text, at)
            if res is not None: return l, (key, res)
        return (0, None)


    def unify_line(self, parts, text, tfrom):
        results = []
        for part in parts:
            tfrom, res = self.unify_key(part, text, tfrom)
            if res is None: return tfrom, None
            results.append(res)
        return tfrom, results

Он принимает грамматики в форме словаря Python с нетерминалами в качестве ключей и альтернатив в качестве элементов массива, и каждая альтернатива представляет собой последовательность выражений. Ниже приведен пример грамматики. 

term_grammar = {
    'expr': [
        ['term', 'add_op', 'expr'],
        ['term']],
    'term': [
        ['fact', 'mul_op', 'term'],
        ['fact']],
    'fact': [
        ['digits'],
        ['(','expr',')']],
    'digits': [
        ['digit','digits'],
        ['digit']],
    'digit': [[str(i)] for i in list(range(10))],
    'add_op': [['+'], ['-']],
    'mul_op': [['*'], ['/']]
}

Вот драйвер: 

import sys
def main(to_parse):
    result = peg_parse(term_grammar).unify_key('expr', to_parse)
    assert (len(to_parse) - result[0]) == 0
    print(result[1])

if __name__ == '__main__': main(sys.argv[1])

Который может быть вызван так: 

python3 parser.py '1+2'
('expr', 
    [('term', 
       [('fact', 
           [('digits', [('digit', [('1', [])])])])]), 
     ('add_op', [('+', [])]), 
     ('expr', 
       [('term', [('fact', [('digits', [('digit', [('2', [])])])])])])])

При разборе грамматик выражений нужно позаботиться о том, чтобы написать: порядок альтернатив важен (в отличие от грамматики без контекста, альтернативы являются упорядоченным выбором, при котором первый выбор пробуется первым, а второй - только если первый матч). Однако они могут представлять все известные контекстно-свободные грамматики.

Если, с другой стороны, вы решите использовать контекстно-свободную грамматику, Earley Parser является одним из самых простых.

Страница:
...