EBNFcompiler.py 21.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#!/usr/bin/python3

"""EBNFcompiler.py - EBNF -> Python-Parser compilation for DHParser

Copyright 2016  by Eckhart Arnold (arnold@badw.de)
                Bavarian Academy of Sciences an Humanities (badw.de)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.  See the License for the specific language governing
permissions and limitations under the License.
"""

Eckhart Arnold's avatar
Eckhart Arnold committed
21
# import collections
22 23 24 25 26 27 28
import keyword
from functools import partial
try:
    import regex as re
except ImportError:
    import re

29 30 31
from .__init__ import __version__
from .toolkit import load_if_file, escape_re, md5, sane_parser_name
from .parsercombinators import GrammarBase, mixin_comment, Forward, RE, NegativeLookahead, \
32
    Alternative, Sequence, Optional, Required, OneOrMore, ZeroOrMore, Token, CompilerBase
33
from .syntaxtree import Node, remove_enclosing_delimiters, reduce_single_child, \
di68kap's avatar
di68kap committed
34 35
    replace_by_single_child, TOKEN_KEYWORD, remove_expendables, remove_tokens, flatten, \
    WHITESPACE_KEYWORD
36 37


Eckhart Arnold's avatar
Eckhart Arnold committed
38 39 40 41 42
__all__ = ['EBNFGrammar',
           'EBNFTransTable',
           'EBNFCompilerError',
           # 'Scanner',
           'EBNFCompiler']
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115


class EBNFGrammar(GrammarBase):
    r"""Parser for an EBNF source file, with this grammar:

    # EBNF-Grammar in EBNF

    @ comment    =  /#.*(?:\n|$)/                    # comments start with '#' and eat all chars up to and including '\n'
    @ whitespace =  /\s*/                            # whitespace includes linefeed
    @ literalws  =  right                            # trailing whitespace of literals will be ignored tacitly

    syntax     =  [~//] { definition | directive } §EOF
    definition =  symbol §"=" expression
    directive  =  "@" §symbol §"=" ( regexp | literal | list_ )

    expression =  term { "|" term }
    term       =  { factor }+
    factor     =  [flowmarker] [retrieveop] symbol !"="   # negative lookahead to be sure it's not a definition
                | [flowmarker] literal
                | [flowmarker] regexp
                | [flowmarker] group
                | [flowmarker] oneormore
                | repetition
                | option

    flowmarker =  "!"  | "&"  | "§" |                # '!' negative lookahead, '&' positive lookahead, '§' required
                  "-!" | "-&"                        # '-' negative lookbehind, '-&' positive lookbehind
    retrieveop =  "::" | ":"                         # '::' pop, ':' retrieve

    group      =  "(" expression §")"
    option     =  "[" expression §"]"
    oneormore  =  "{" expression "}+"
    repetition =  "{" expression §"}"

    symbol     =  /(?!\d)\w+/~                       # e.g. expression, factor, parameter_list
    literal    =  /"(?:[^"]|\\")*?"/~                # e.g. "(", '+', 'while'
                | /'(?:[^']|\\')*?'/~                # whitespace following literals will be ignored tacitly.
    regexp     =  /~?\/(?:[^\/]|(?<=\\)\/)*\/~?/~    # e.g. /\w+/, ~/#.*(?:\n|$)/~
                                                     # '~' is a whitespace-marker, if present leading or trailing
                                                     # whitespace of a regular expression will be ignored tacitly.
    list_      =  /\w+\s*(?:,\s*\w+\s*)*/~           # comma separated list of symbols, e.g. BEGIN_LIST, END_LIST,
                                                     # BEGIN_QUOTE, END_QUOTE ; see CommonMark/markdown.py for an exmaple
    EOF =  !/./
    """
    expression = Forward()
    source_hash__ = "1065c2e43262a5cb3aa438ec4d347c32"
    parser_initialization__ = "upon instatiation"
    wsp__ = mixin_comment(whitespace=r'\s*', comment=r'#.*(?:\n|$)')
    wspL__ = ''
    wspR__ = wsp__
    EOF = NegativeLookahead(RE('.', wR=''))
    list_ = RE('\\w+\\s*(?:,\\s*\\w+\\s*)*')
    regexp = RE('~?/(?:[^/]|(?<=\\\\)/)*/~?')
    literal = Alternative(RE('"(?:[^"]|\\\\")*?"'), RE("'(?:[^']|\\\\')*?'"))
    symbol = RE('(?!\\d)\\w+')
    repetition = Sequence(Token("{"), expression, Required(Token("}")))
    oneormore = Sequence(Token("{"), expression, Token("}+"))
    option = Sequence(Token("["), expression, Required(Token("]")))
    group = Sequence(Token("("), expression, Required(Token(")")))
    retrieveop = Alternative(Token("::"), Token(":"))
    flowmarker = Alternative(Token("!"), Token("&"), Token("§"), Token("-!"), Token("-&"))
    factor = Alternative(Sequence(Optional(flowmarker), Optional(retrieveop), symbol, NegativeLookahead(Token("="))),
                         Sequence(Optional(flowmarker), literal), Sequence(Optional(flowmarker), regexp),
                         Sequence(Optional(flowmarker), group), Sequence(Optional(flowmarker), oneormore), repetition,
                         option)
    term = OneOrMore(factor)
    expression.set(Sequence(term, ZeroOrMore(Sequence(Token("|"), term))))
    directive = Sequence(Token("@"), Required(symbol), Required(Token("=")), Alternative(regexp, literal, list_))
    definition = Sequence(symbol, Required(Token("=")), expression)
    syntax = Sequence(Optional(RE('', wR='', wL=wsp__)), ZeroOrMore(Alternative(definition, directive)), Required(EOF))
    root__ = syntax


di68kap's avatar
di68kap committed
116
EBNF_ASTTransform = {
117 118 119 120 121 122 123 124 125 126 127 128 129
    # AST Transformations for EBNF-grammar
    "syntax":
        remove_expendables,
    "directive, definition":
        partial(remove_tokens, tokens={'@', '='}),
    "expression, chain":
        [replace_by_single_child, flatten,
         partial(remove_tokens, tokens={'|', '--'})],
    "term":
        [replace_by_single_child, flatten],  # supports both idioms:  "{ factor }+" and "factor { factor }"
    "factor, flowmarker, retrieveop":
        replace_by_single_child,
    "group":
130 131 132
        [remove_enclosing_delimiters, replace_by_single_child],
    "oneormore, repetition, option, regexchain":
        [reduce_single_child, remove_enclosing_delimiters],
133
    "symbol, literal, regexp":
134 135 136
        [remove_expendables, reduce_single_child],
    (TOKEN_KEYWORD, WHITESPACE_KEYWORD):
        [remove_expendables, reduce_single_child],
137 138
    "list_":
        [partial(remove_tokens, tokens={','})],
139 140 141 142 143
    "":
        [remove_expendables, replace_by_single_child]
}


di68kap's avatar
di68kap committed
144 145 146
EBNF_ASTPipeline = [EBNF_ASTTransform]


147 148 149 150 151 152
class EBNFCompilerError(Exception):
    """Error raised by `EBNFCompiler` class. (Not compilation errors
    in the strict sense, see `CompilationError` below)"""
    pass


Eckhart Arnold's avatar
Eckhart Arnold committed
153 154
# Scanner = collections.namedtuple('Scanner',
#                                  'symbol instantiation_call cls_name cls')
155 156 157 158 159 160 161


class EBNFCompiler(CompilerBase):
    """Generates a Parser from an abstract syntax tree of a grammar specified
    in EBNF-Notation.
    """
    COMMENT_KEYWORD = "COMMENT__"
162
    DEFAULT_WHITESPACE = r'[\t ]*'
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
    RESERVED_SYMBOLS = {TOKEN_KEYWORD, WHITESPACE_KEYWORD, COMMENT_KEYWORD}
    KNOWN_DIRECTIVES = {'comment', 'whitespace', 'tokens', 'literalws'}
    VOWELS = {'A', 'E', 'I', 'O', 'U'}  # what about cases like 'hour', 'universe' etc.?
    AST_ERROR = "Badly structured syntax tree. " \
                "Potentially due to erroneuos AST transformation."
    PREFIX_TABLE = [('§', 'Required'), ('&', 'Lookahead'),
                    ('!', 'NegativeLookahead'), ('-&', 'Lookbehind'),
                    ('-!', 'NegativeLookbehind'), ('::', 'Pop'),
                    (':', 'Retrieve')]

    def __init__(self, grammar_name="", source_text=""):
        super(EBNFCompiler, self).__init__()
        assert grammar_name == "" or re.match('\w+\Z', grammar_name)
        self.grammar_name = grammar_name
        self.source_text = load_if_file(source_text)
        self._reset()

    def _reset(self):
        self.rules = set()
        self.symbols = set()
        self.variables = set()
        self.scanner_tokens = set()
        self.definition_names = []
        self.recursive = set()
        self.root = ""
188
        self.directives = {'whitespace': self.DEFAULT_WHITESPACE,
189
                           'comment': '',
190
                           'literalws': ['right']}
191 192 193 194 195 196 197 198 199

    def gen_scanner_skeleton(self):
        name = self.grammar_name + "Scanner"
        return "def %s(text):\n    return text\n" % name

    def gen_AST_skeleton(self):
        if not self.definition_names:
            raise EBNFCompilerError('Compiler has not been run before calling '
                                    '"gen_AST_Skeleton()"!')
di68kap's avatar
di68kap committed
200 201 202
        tt_name = self.grammar_name + '_ASTTransform'
        pl_name = self.grammar_name + '_ASTPipeline'
        transtable = [tt_name + ' = {',
203 204 205
                      '    # AST Transformations for the ' +
                      self.grammar_name + '-grammar']
        for name in self.definition_names:
di68kap's avatar
di68kap committed
206
            transtable.append('    "' + name + '": no_operation,')
207
        transtable += ['    "": no_operation', '}', '',  pl_name + ' = [%s]' % tt_name, '']
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
        return '\n'.join(transtable)

    def gen_compiler_skeleton(self):
        if not self.definition_names:
            raise EBNFCompilerError('Compiler has not been run before calling '
                                    '"gen_Compiler_Skeleton()"!')
        compiler = ['class ' + self.grammar_name + 'Compiler(CompilerBase):',
                    '    """Compiler for the abstract-syntax-tree of a ' +
                    self.grammar_name + ' source file.',
                    '    """', '',
                    '    def __init__(self, grammar_name="' +
                    self.grammar_name + '"):',
                    '        super(' + self.grammar_name +
                    'Compiler, self).__init__()',
                    "        assert re.match('\w+\Z', grammar_name)", '']
        for name in self.definition_names:
            if name == self.root:
                compiler += ['    def ' + name + '(self, node):',
                             '        return node', '']
            else:
                compiler += ['    def ' + name + '(self, node):',
                             '        pass', '']
230
        return '\n'.join(compiler)
231 232 233 234 235 236 237 238 239 240

    def gen_parser(self, definitions):
        # fix capture of variables that have been defined before usage [sic!]
        if self.variables:
            for i in range(len(definitions)):
                if definitions[i][0] in self.variables:
                    definitions[i] = (definitions[i][0], 'Capture(%s, "%s")' %
                                      (definitions[1], definitions[0]))

        self.definition_names = [defn[0] for defn in definitions]
Eckhart Arnold's avatar
Eckhart Arnold committed
241 242 243 244
        definitions.append(('wspR__', WHITESPACE_KEYWORD
                            if 'right' in self.directives['literalws'] else "''"))
        definitions.append(('wspL__', WHITESPACE_KEYWORD
                            if 'left' in self.directives['literalws'] else "''"))
245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
        definitions.append((WHITESPACE_KEYWORD,
                            ("mixin_comment(whitespace="
                             "r'{whitespace}', comment=r'{comment}')").
                            format(**self.directives)))
        definitions.append((self.COMMENT_KEYWORD, "r'{comment}'".format(**self.directives)))

        # prepare parser class header and docstring and
        # add EBNF grammar to the doc string of the parser class
        article = 'an ' if self.grammar_name[0:1].upper() \
                           in EBNFCompiler.VOWELS else 'a '
        declarations = ['class ' + self.grammar_name +
                        'Grammar(GrammarBase):',
                        'r"""Parser for ' + article + self.grammar_name +
                        ' source file' +
                        (', with this grammar:' if self.source_text else '.')]
        definitions.append(('parser_initialization__', '"upon instatiation"'))
        if self.source_text:
            definitions.append(('source_hash__',
                                '"%s"' % md5(self.source_text, __version__)))
            declarations.append('')
            declarations += [line for line in self.source_text.split('\n')]
            while declarations[-1].strip() == '':
                declarations = declarations[:-1]
        declarations.append('"""')

        # turn definitions into declarations in reverse order
        self.root = definitions[0][0] if definitions else ""
        definitions.reverse()
        declarations += [symbol + ' = Forward()'
                         for symbol in sorted(list(self.recursive))]
        for symbol, statement in definitions:
            if symbol in self.recursive:
                declarations += [symbol + '.set(' + statement + ')']
            else:
                declarations += [symbol + ' = ' + statement]
        for nd in self.symbols:
            if nd.result not in self.rules:
                nd.add_error("Missing production for symbol '%s'" % nd.result)
        if self.root and 'root__' not in self.symbols:
            declarations.append('root__ = ' + self.root)
        declarations.append('')
        return '\n    '.join(declarations)

    def syntax(self, node):
        self._reset()
        definitions = []

        # drop the wrapping sequence node
        if isinstance(node.parser, Sequence) and \
                isinstance(node.result[0].parser, ZeroOrMore):
            node = node.result[0]

        # compile definitions and directives and collect definitions
        for nd in node.result:
            if nd.parser.name == "definition":
                definitions.append(self.compile__(nd))
            else:
                assert nd.parser.name == "directive", nd.as_sexpr()
                self.compile__(nd)

        return self.gen_parser(definitions)

    def definition(self, node):
        rule = node.result[0].result
        if rule in EBNFCompiler.RESERVED_SYMBOLS:
            node.add_error('Symbol "%s" is a reserved symbol.' % rule)
        elif not sane_parser_name(rule):
            node.add_error('Illegal symbol "%s". Symbols must not start or '
                           ' end with a doube underscore "__".' % rule)
        elif rule in self.scanner_tokens:
            node.add_error('Symbol "%s" has already been defined as '
                           'a scanner token.' % rule)
        elif keyword.iskeyword(rule):
            node.add_error('Python keyword "%s" may not be used as a symbol. '
                           % rule + '(This may change in the furute.)')
        elif rule in self.rules:
            node.add_error('A rule with name "%s" has already been defined.' %
                           rule)
        try:
            self.rules.add(rule)
            defn = self.compile__(node.result[1])
            if rule in self.variables:
                defn = 'Capture(%s, "%s")' % (defn, rule)
                self.variables.remove(rule)
        except TypeError as error:
            errmsg = EBNFCompiler.AST_ERROR + " (" + str(error) + ")\n" + node.as_sexpr()
            node.add_error(errmsg)
            rule, defn = rule + ':error', '"' + errmsg + '"'
Eckhart Arnold's avatar
Eckhart Arnold committed
333
        return rule, defn
334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352

    @staticmethod
    def _check_rx(node, rx):
        """Checks whether the string `rx` represents a valid regular
        expression. Makes sure that multiline regular expressions are
        prepended by the multiline-flag. Returns the regular expression string.
        """
        rx = rx if rx.find('\n') < 0 or rx[0:4] == '(?x)' else '(?x)' + rx
        try:
            re.compile(rx)
        except Exception as re_error:
            node.add_error("malformed regular expression %s: %s" %
                           (repr(rx), str(re_error)))
        return rx

    def directive(self, node):
        key = node.result[0].result.lower()
        assert key not in self.scanner_tokens
        if key in {'comment', 'whitespace'}:
353 354
            if node.result[1].parser.name == "list_":
                if len(node.result[1].result) != 1:
Eckhart Arnold's avatar
Eckhart Arnold committed
355
                    node.add_error('Directive "%s" must have one, but not %i values.' %
356 357 358 359 360
                                   (key, len(node.result[1])))
                value = self.compile__(node.result[1]).pop()
                if value in {'linefeed', 'standard'} and key == 'whitespace':
                    value = '\s*' if value == "linefeed" else self.DEFAULT_WHITESPACE
                else:
Eckhart Arnold's avatar
Eckhart Arnold committed
361
                    node.add_error('Value "%" not allowed for directive "%s".' % (value, key))
362
            else:
363 364 365 366 367 368 369 370
                value = node.result[1].result.strip("~")
                if value != node.result[1].result:
                    node.add_error("Whitespace marker '~' not allowed in definition of "
                                   "%s regular expression." % key)
                if value[0] + value[-1] in {'""', "''"}:
                    value = escape_re(value[1:-1])
                elif value[0] + value[-1] == '//':
                    value = self._check_rx(node, value[1:-1])
371 372 373 374
            self.directives[key] = value
        elif key == 'literalws':
            value = {item.lower() for item in self.compile__(node.result[1])}
            if (len(value - {'left', 'right', 'both', 'none'}) > 0
Eckhart Arnold's avatar
Eckhart Arnold committed
375
                    or ('none' in value and len(value) > 1)):
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
                node.add_error('Directive "literalws" allows the values '
                               '`left`, `right`, `both` or `none`, '
                               'but not `%s`' % ", ".join(value))
            ws = {'left', 'right'} if 'both' in value \
                else {} if 'none' in value else value
            self.directives[key] = list(ws)

        elif key == 'tokens':
            self.scanner_tokens |= self.compile__(node.result[1])
        else:
            node.add_error('Unknown directive %s ! (Known ones are %s .)' %
                           (key,
                            ', '.join(list(EBNFCompiler.KNOWN_DIRECTIVES))))
        return ""

    def non_terminal(self, node, parser_class):
        """Compiles any non-terminal, where `parser_class` indicates the Parser class
        name for the particular non-terminal.
        """
        arguments = filter(lambda arg: arg,
                           [self.compile__(r) for r in node.result])
        return parser_class + '(' + ', '.join(arguments) + ')'

    def expression(self, node):
        return self.non_terminal(node, 'Alternative')

    def term(self, node):
        return self.non_terminal(node, 'Sequence')

    def factor(self, node):
        assert isinstance(node.parser, Sequence), node.as_sexpr()  # these assert statements can be removed
        assert node.children
        assert len(node.result) >= 2, node.as_sexpr()
        prefix = node.result[0].result

        arg = node.result[-1]
        if prefix in {'::', ':'}:
            assert len(node.result) == 2
            if arg.parser.name != 'symbol':
                node.add_error(('Retrieve Operator "%s" requires a symbols, '
                                'and not a %s.') % (prefix, str(arg.parser)))
                return str(arg.result)
            self.variables.add(arg.result)

        if len(node.result) > 2:
            # shift = (Node(node.parser, node.result[1].result),)
            # node.result[1].result = shift + node.result[2:]
            node.result[1].result = (Node(node.result[1].parser,
                                          node.result[1].result),) \
                                    + node.result[2:]
            node.result[1].parser = node.parser
            node.result = (node.result[0], node.result[1])

        node.result = node.result[1:]
        for match, parser_class in self.PREFIX_TABLE:
            if prefix == match:
                return self.non_terminal(node, parser_class)

        assert False, ("Unknown prefix %s \n" % prefix) + node.as_sexpr()

    def option(self, node):
        return self.non_terminal(node, 'Optional')

    def repetition(self, node):
        return self.non_terminal(node, 'ZeroOrMore')

    def oneormore(self, node):
        return self.non_terminal(node, 'OneOrMore')

445 446 447
    def regexchain(self, node):
        raise EBNFCompilerError("Not yet implemented!")

448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473
    def group(self, node):
        raise EBNFCompilerError("Group nodes should have been eliminated by "
                                "AST transformation!")

    def symbol(self, node):
        if node.result in self.scanner_tokens:
            return 'ScannerToken("' + node.result + '")'
        else:
            self.symbols.add(node)
            if node.result in self.rules:
                self.recursive.add(node.result)
            return node.result

    def literal(self, node):
        return 'Token(' + ', '.join([node.result]) + ')'

    def regexp(self, node):
        rx = node.result
        name = []
        if rx[:2] == '~/':
            if not 'left' in self.directives['literalws']:
                name = ['wL=' + WHITESPACE_KEYWORD] + name
            rx = rx[1:]
        elif 'left' in self.directives['literalws']:
            name = ["wL=''"] + name
        if rx[-2:] == '/~':
Eckhart Arnold's avatar
Eckhart Arnold committed
474
            if 'right' not in self.directives['literalws']:
475 476 477 478 479 480 481 482 483 484 485 486 487 488
                name = ['wR=' + WHITESPACE_KEYWORD] + name
            rx = rx[:-1]
        elif 'right' in self.directives['literalws']:
            name = ["wR=''"] + name
        try:
            arg = repr(self._check_rx(node, rx[1:-1].replace(r'\/', '/')))
        except AttributeError as error:
            errmsg = EBNFCompiler.AST_ERROR + " (" + str(error) + ")\n" + \
                     node.as_sexpr()
            node.add_error(errmsg)
            return '"' + errmsg + '"'
        return 'RE(' + ', '.join([arg] + name) + ')'

    def list_(self, node):
489 490
        assert node.children
        return set(item.result.strip() for item in node.result)