Ката – то вправа в східних бойових мистецтвах, набір рухів які треба повторювати поки не засвоїш досконально. Термін застосовується також і для неробочого, неспортивного, самостійного учбового програмування поза якимось проектом.
На моєму домашньому модемі відвалився 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()
І я зрозумів дві речі: що найбільше на світі (якщо не враховувати сну) люблю писати код, і що таке множина 
digit = "0" | "1"
number = digit {digit}
first(number) = {"0", "1"}
І ми знаємо що парсер може прочитати не будь-яку граматику, а лише ту, в якої для кожного виразу на зразок
definition = exp1 | exp2
Виконується умова:
Таким чином отака граматика багатозначна:
sum = number | sum ("+" | "-") sum
Бо вираз 1 – 10 + 11 можна розпарсити як (1 – 10) + 11 або як 1 – (10 + 11). А все тому, що 
Її можна переписати так щоб в правилі для суми не було двох варіантів що починаються з однакових символів.
sum = number {("+" | "-") number}
Так вся сума розгортатиметься зразу і не буде проблем з тим яку операцію виконувати швидше.
Тепер би ще змусити його автоматично генерувати код парсера за EBNF і вийде власний YACC. :)
Filed under: Кодерство Tagged: Python
