Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

EBNF Parser Kata

with 2 comments

Ката – то вправа в східних бойових мистецтвах, набір рухів які треба повторювати поки не засвоїш досконально. Термін застосовується також і для неробочого, неспортивного, самостійного учбового програмування поза якимось проектом.

На моєму домашньому модемі відвалився DSL, то я вчора ввечері не мав чим зайнятись. (Хоча звісно є купа важливіших речей) Зате біля мене була роздруківка книжечки Ніклауса Вірта “Compiler Construction“, то я взявся перекладати його парсер EBNF що ілюструє метод рекурсивного спуску з Oberon на Python. Вийшло ніби незле:

# ebnf.py
import re

class Symbol(object):
    instances = {}
    def __init__(self, name, pattern):
        self.pattern = pattern
        self.regexp = re.compile(pattern)
        self.instances[name] = self

    def match(self, text):
        text = text.lstrip()
        m = self.regexp.match(text)
        if m:
            return m.group(), text[len(m.group()):]

    @classmethod
    def get_next(cls, text):
        if not text.strip():
            return 'empty', '', ''
        for name, sym in cls.instances.items():
            m = sym.match(text)
            if m:
                return name, m[0], m[1]
        raise UnknownSymbolError('Unknown symbol: %r' % text[:50] + (
            '...' if len(text) > 50 else ''
        ))

Symbol('ident', '\w+')
Symbol('literal', '"[^"]*"')
Symbol('eql', '=')
Symbol('lparen', '\(')
Symbol('rparen', '\)')
Symbol('lbrak', '\[')
Symbol('rbrak', '\]')
Symbol('lbrace', '\{')
Symbol('rbrace', '\}')
Symbol('bar', '\|')
Symbol('period', '\.')

EBNF = '''
syntax = {production}.
production = identifier "=" expression ".".
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
'''

def parse_ebnf(text):
    sym, sym_text, remaining = '', '', text
    
    def next():
        nonlocal sym, sym_text, remaining
        sym, sym_text, remaining = Symbol.get_next(remaining)

    next()
    
    def syntax():
        res = ['syntax']
        while sym == 'ident':
            res.append(production())
        return res

    def production():
        name = sym_text
        next()
        if sym == 'eql':
            next()
        else:
            raise ExpectedEqualityError
        exp = expression()
        if sym == 'period':
            next()
        else:
            raise NoPeriodError
        return ['production', name, exp]

    def expression():
        res = ['expression', term()]
        while sym == 'bar':
            next()
            res.append(term())
        return res

    def term():
        res = ['term']
        while sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace'):
            res.append(factor())
        if len(res) == 1:
            raise NoFactorError
        return res

    def factor():
        if sym == 'ident':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'literal':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'lparen':
            next()
            exp = expression()
            if sym == 'rparen':
                next()
            else:
                raise NoRParenError
            return ['(', exp]
        elif sym == 'lbrak':
            next()
            exp = expression()
            if sym == 'rbrak':
                next()
            else:
                raise NoRBrakError
            return ['[', exp]
        elif sym == 'lbrace':
            next()
            exp = expression()
            if sym == 'rbrace':
                next()
            else:
                raise NoRBraceError
            return ['{', exp]
        else:
            raise RuntimeError(
                "term should be called only when "
                "sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace')"
            )

    return syntax()

class UnknownSymbolError(SyntaxError):
    pass

class NoPeriodError(SyntaxError):
    pass

class NoRParenError(SyntaxError):
    pass

class NoRBrakError(SyntaxError):
    pass

class NoRBraceError(SyntaxError):
    pass

class NoFactorError(SyntaxError):
    pass

class ExpectedEqualityError(SyntaxError):
    pass

Трохи TDD, трохи дописування тестів після:

# test.py
from unittest import TestCase, main, skip

from ebnf import Symbol
from ebnf import parse_ebnf, EBNF
from ebnf import print_tree
from ebnf import (
    NoPeriodError, NoRParenError, UnknownSymbolError,
    NoRBrakError, NoRBraceError, NoFactorError
)

class TestSymbol(TestCase):
    def test_paren(self):
        self.assertEqual(
            Symbol.get_next('(asdf)'),
            ('lparen', '(', 'asdf)')
        )
    def test_ident(self):
        self.assertEqual(
            Symbol.get_next('asdf'),
            ('ident', 'asdf', '')
        )
    def test_bar(self):
        self.assertEqual(
            Symbol.get_next('|asdf'),
            ('bar', '|', 'asdf')
        )

class TestEBNF(TestCase):
    def test_self(self):
        tree = parse_ebnf(EBNF)
        self.assertEqual(
            parse_ebnf(EBNF),
            ['syntax',
             ['production',
              'syntax',
              ['expression',
               ['term', ['{', ['expression', ['term', ['ident', 'production']]]]]]],
             ['production',
              'production',
              ['expression',
               ['term',
                ['ident', 'identifier'],
                ['literal', '"="'],
                ['ident', 'expression'],
                ['literal', '"."']]]],
             ['production',
              'expression',
              ['expression',
               ['term',
                ['ident', 'term'],
                ['{', ['expression', ['term', ['literal', '"|"'], ['ident', 'term']]]]]]],
             ['production',
              'term',
              ['expression',
               ['term',
                ['ident', 'factor'],
                ['{', ['expression', ['term', ['ident', 'factor']]]]]]],
             ['production',
              'factor',
              ['expression',
               ['term', ['ident', 'identifier']],
               ['term', ['ident', 'string']],
               ['term', ['literal', '"("'], ['ident', 'expression'], ['literal', '")"']],
               ['term', ['literal', '"["'], ['ident', 'expression'], ['literal', '"]"']],
               ['term', ['literal', '"{"'], ['ident', 'expression'], ['literal', '"}"']]]]]
        )

    def test_without_period(self):
        with self.assertRaises(NoPeriodError):
            parse_ebnf('symbol = "asdf"')

    def test_without_rparen(self):
        with self.assertRaises(NoRParenError):
            parse_ebnf('symbol = ("asdf"')

    def test_without_rbrak(self):
        with self.assertRaises(NoRBrakError):
            parse_ebnf('symbol = ["asdf"')

    def test_without_rbrace(self):
        with self.assertRaises(NoRBraceError):
            parse_ebnf('symbol = {literal')

    def test_unknown_symbol(self):
        with self.assertRaises(UnknownSymbolError):
            parse_ebnf('!symbol = "asdf"')

    def test_no_factor(self):
        with self.assertRaises(NoFactorError):
            parse_ebnf('sym = ||')

    def test_for_binary(self):
        self.assertEqual(
            parse_ebnf('''
                digit = "0"|"1".
                number = digit {digit}.
            '''),
            ['syntax',
             ['production',
              'digit',
              ['expression', ['term', ['literal', '"0"']], ['term', ['literal', '"1"']]]],
             ['production',
              'number',
              ['expression',
               ['term',
                ['ident', 'digit'],
                ['{', ['expression', ['term', ['ident', 'digit']]]]]]]]
        )


if __name__ == '__main__':
    main()

І я зрозумів дві речі: що найбільше на світі (якщо не враховувати сну) люблю писати код, і що таке множина first_1(k). Якщо коротко, то це множина символів з яких може починатись рядок що виводиться з нетерміналу k. Наприклад:

digit = "0" | "1"
number = digit {digit}

first(number) = {"0", "1"}

І ми знаємо що парсер може прочитати не будь-яку граматику, а лише ту, в якої для кожного виразу на зразок

definition = exp1 | exp2

Виконується умова:

first_1(exp1) \cap first_1(exp2) = \varnothing

Таким чином отака граматика багатозначна:

sum = number | sum ("+" | "-") sum

Бо вираз 1 – 10 + 11 можна розпарсити як (1 – 10) + 11 або як 1 – (10 + 11). А все тому, що first(number) = first(sum).

Її можна переписати так щоб в правилі для суми не було двох варіантів що починаються з однакових символів.

sum = number {("+" | "-") number}

Так вся сума розгортатиметься зразу і не буде проблем з тим яку операцію виконувати швидше.

Тепер би ще змусити його автоматично генерувати код парсера за EBNF і вийде власний YACC. 🙂

Advertisements

Written by bunyk

Серпень 4, 2015 at 10:19

Оприлюднено в Кодерство

Tagged with

Відповідей: 2

Subscribe to comments with RSS.

  1. Бачиш, які дива робить неробочий модем!

    А взагалі, у тебе порядок оголошення терміналів впливає на те, яка буде послідовність лексем. Тобто, для прикладу, якщо ‘if’ був би виразом для терміналу keyword, то ідентифікатор ‘ifaddr’ міг би парситись як ‘if’ з remaining ‘addr’, здається. Поки немає конфліктів між регулярними виразами (термінали всі починаються із різних символів), то нормально.

    Генерація скінченних автоматів для парсингу це досить хороша вправа, колись робив її на Схемі (https://github.com/EarlGray/SECD/blob/master/tests/regex.scm — тут крихітний движок регулярних виразів), на Пітоні із його батарейками має бути набагато легше.

    dmytrish

    Серпень 4, 2015 at 12:24

    • До речі, так, треба переписати лексичний аналізатор. 🙂

      bunyk

      Серпень 4, 2015 at 12:43


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: