Programy pro generování syntaktických analyzátorů čtou ze vstupu popis gramatiky a vytvářejí zdrojový text parseru.
Začneme syntaktických analyzátory, které pouze rozpoznávají daný jazyk.
Tj. rozhodnou, zda vstupní zdrojový text vyhovuje zadané gramatice.
Podívejme se na jedno gramatické pravidlo ze zadané gramatiky:
if_stat : "if" "(" expr ")" stat ( "else" stat )? ;
Generátor vytvoří třídu Parser a v ní pro zmíněné pravidlo metodu parse_if_stat
from lexer import Lexer class Parser (Lexer) : def parse_if_stat (self) : self.check ("if") self.check ("(") self.parse_expr () self.check (")") self.parse_stat () if self.tokenText == "else" : self.check ("else") self.parse_stat ()
Metoda zkontroluje přítomnost terminálů.
Pro neterminály zavolá odpovídající metody.
Rozhodování, kterou alternativou budeme pokračovat, se řídí množinami symbolů, kterými jednotlivé alternativy začínají.
Nebo vygenerovaný parser v jazyce C++
void CmmParser::parse_if_stat () { match (KEYWORD_if); match (LPAREN); parse_expr (); match (RPAREN); parse_stat (); if (isSymbol (KEYWORD_else)) { nextSymbol (); parse_stat (); } }
Program v jazyce Python generující syntaktický analyzátor také v jazyce Python.
( V této kapitole je použita varanta s konstantou generate_tree = False )
while_stat : "while" "(" expr ")" stat ; if_stat : "if" "(" expr ")" stat ( "else" stat )? ; compound_stat : "{" ( stat )* "}" ; simple_stat : expr ";" ; empty_stat : ";" ; stat : while_stat | if_stat | compound_stat | simple_stat | empty_stat ; simple_expr : identifier | number | "(" expr ")" ; mult_expr : simple_expr ( ("*"|"/") simple_expr )* ; add_expr : mult_expr ( ("+"|"-") mult_expr )* ; expr : add_expr ( "=" expr )? ; program : stat;
Vytvořená třída Parser je odvozená od lexikálního analyzátoru.
již popsaný mimimální lexikální analyzátor
Kompletní zdojový text http://gitlab.fjfi.cvut.cz/culikzde/simple-view/-/blob/master/tutorial/plain-grammar/plain_lexer.py
from plain_lexer import Lexer class Parser (Lexer) :
V konstruktoru jsou očíslovány terminální symboly.
def __init__ (self) : super (Parser, self).__init__ () # eos = 0 # identifier = 1 # number = 2 # real_number = 3 # character_literal = 4 # string_literal = 5 # separator = 6 # end_of_line = 7 self.keyword_else = 8 self.keyword_if = 9 self.keyword_while = 10 # ( 11 # ) 12 # * 13 # + 14 # , 15 # - 16 # / 17 # ; 18 # { 19 # } 20 self.set_0 = self.alloc ([self.identifier, self.number, self.keyword_if, self.keyword_while, 11, 18, 19]) # identifier number if while ( ; {
Virtuální funkce lookupKeyword volaná lexer po přečtení identifikátoru,
převádí některé idntifikátory na klíčová slova
def lookupKeyword (self) : s = self.tokenText n = len (s) if n == 2 : if s[0:2] == "if" : self.token = self.keyword_if elif n == 4 : if s[0:4] == "else" : self.token = self.keyword_else elif n == 5 : if s[0:5] == "while" : self.token = self.keyword_while
Funkce processSeparator rozpoznává oddělovače.
def processSeparator (self) : if self.tokenText == '(' : self.token = 11 if self.tokenText == ')' : self.token = 12 if self.tokenText == '*' : self.token = 13 if self.tokenText == '+' : self.token = 14 if self.tokenText == ',' : self.token = 15 if self.tokenText == '-' : self.token = 16 if self.tokenText == '/' : self.token = 17 if self.tokenText == ';' : self.token = 18 if self.tokenText == '{' : self.token = 19 if self.tokenText == '}' : self.token = 20 if self.token == self.separator : self.error ("Unknown separator")
Pomocná funkce tokenToString se hodí při zobrazování chyb
def tokenToString (self, value) : if value == 0: return "<end of source text>" if value == 1: return "<identifier>" if value == 2: return "<number>" # ... if value == 9: return "if" if value == 10: return "while" if value == 11: return "(" if value == 12: return ")" # ...
Funkce storeLocation ukládá číslo řádky ze zdrojového textu používané například navigačními stromy
def storeLocation (self, item) : item.src_line = self.tokenLineNum item.src_column = self.tokenColNum item.src_pos = self.tokenByteOfs item.src_end = self.charByteOfs
Podívejme se jak se využívají množiny symbolů z předchozí kapitoly, při výběru alternativy.
def parse_add_expr (self) : self.parse_mult_expr () while self.tokenText == "+" or self.tokenText == "-" : if self.tokenText == "+" : self.check ("+") elif self.tokenText == "-" : self.check ("-") else : self.error ("Unexpected token") self.parse_mult_expr ()
Pokud pro některou alternativu má množina dva nebo tři prvky, vygenerujeme podmínku pomocí několika or.
def parse_stat (self) : if self.tokenText == "while" : self.parse_while_stat () elif self.tokenText == "if" : self.parse_if_stat () elif self.tokenText == "{" : self.parse_compound_stat () elif self.token == identifier or self.token == number or self.tokenText == "(" : self.parse_simple_stat () elif self.tokenText == ";" : self.parse_empty_stat () else : self.error ("Unexpected token")
V případě větší množiny vygenerujeme konstantu (pole set_0) a používáme ji pro testování.
( Funkce register_collection v http://gitlab.fjfi.cvut.cz/culikzde/view/-/blob/master/tutorial/plain-grammar/plain_toparser.py#L177 )
def parse_compound_stat (self) : self.check ("{") while self.set_0 [self.token] : self.parse_stat () self.check ("}")
Zde jsou metody rozpoznávající ostatní pravidla
class Parser (Lexer) : def parse_while_stat (self) : self.check ("while") self.check ("(") self.parse_expr () self.check (")") self.parse_stat () def parse_if_stat (self) : self.check ("if") self.check ("(") self.parse_expr () self.check (")") self.parse_stat () if self.tokenText == "else" : self.check ("else") self.parse_stat () def parse_simple_stat (self) : self.parse_expr () self.check (";") def parse_empty_stat (self) : self.check (";") def parse_simple_expr (self) : if self.token == identifier : self.readIdentifier () elif self.token == number : self.readNumber () elif self.tokenText == "(" : self.check ("(") self.parse_expr () self.check (")") else : self.error ("Unexpected token") def parse_mult_expr (self) : self.parse_simple_expr () while self.tokenText == "*" or self.tokenText == "/" : if self.tokenText == "*" : self.check ("*") elif self.tokenText == "/" : self.check ("/") else : self.error ("Unexpected token") self.parse_simple_expr () def parse_expr (self) : self.parse_add_expr () if self.tokenText == "=" : self.check ("=") self.parse_expr () def parse_program (self) : self.parse_stat ()
http://gitlab.fjfi.cvut.cz/culikzde/view/-/blob/master/tutorial/plain-grammar/plain_view.py
Funkce, která vezme text zadané gramatiky z první záložky,
gramatiku uloží do stromu (parseRules),
vypočítá množiny počátečních symbolů (initSymbols),
a vygeneruje parser (parserFromGrammar).
def createParser (self) : # self.tree.clear () edit = self.getEditor () if edit != None : source = edit.toPlainText () grammar = Grammar () grammar.openString (source) grammar.parseRules () initSymbols (grammar) self.parserFileName = self.outputFileName ("parser.py") self.productFileName = self.outputFileName ("product.py") to_parser = ToParser () to_parser.open (self.parserFileName) to_parser.parserFromGrammar (grammar) to_parser.close () self.readFile (None, self.parserFileName) to_product = ToProduct () to_product.open (self.productFileName) to_product.productFromGrammar (grammar) to_product.close () self.readFile (None, self.productFileName) self.grammarTree (grammar, edit)
Podobně, jako když jsem určovali množiny počátečních symbolů procházíme celou gramatiku uloženou ve stromové podobě.
Pro všechna pravidla vygenerujeme parse_… metodu.
def parserFromRules (self, grammar) : for rule in grammar.rules : self.parserFromRule (grammar, rule) def parserFromRule (self, grammar, rule) : grammar.updatePosition (rule) self.putLn ("def parse_" + rule.name + " (self) :") self.incIndent () self.parserFromExpression (grammar, rule, rule.expr) self.decIndent () self.putEol ()
Pro jednotlivé alternativy napíšeme if příkazy.
def parserFromExpression (self, grammar, rule, expr) : cnt = len (expr.alternatives) inx = 0 start = True for alt in expr.alternatives : if cnt > 1 : cond = self.conditionFromAlternative (grammar, alt) if start : self.put ("if") else : self.put ("elif") start = False self.putLn (" " + cond + " :") self.incIndent () self.parserFromAlternative (grammar, rule, alt) if cnt > 1 : self.decIndent () inx = inx + 1 if cnt > 1 : self.putLn ("else :") self.incIndent () self.putLn ("self.error (" + '"' + "Unexpected token" + '"' + ")") self.decIndent ()
Jednotlivé položky tvořící alternativu zpracujeme jednu po druhé.
def parserFromAlternative (self, grammar, rule, alt) : for item in alt.items : if isinstance (item, Terminal) : self.parserFromTerminal (grammar, rule, item) elif isinstance (item, Nonterminal) : self.parserFromNonterminal (grammar, rule, item) elif isinstance (item, Ebnf) : self.parserFromEbnf (grammar, rule, item) else : grammar.error ("Unknown alternative item: " + item.__class__.__name__)
Pro výraz v závorkách vygenerujeme if nebo while.
def parserFromEbnf (self, grammar, rule, ebnf) : if ebnf.mark == '?' : self.put ("if ") elif ebnf.mark == '*' : self.put ("while ") elif ebnf.mark == '+' : self.put ("while ") if ebnf.mark != "" : cond = self.conditionFromExpression (grammar, ebnf.expr) self.put (cond) self.putLn (" :") self.incIndent () self.parserFromExpression (grammar, rule, ebnf.expr) if ebnf.mark != "" : self.decIndent ()
Pro neterminály zaloláme odpovídající parse_… metodu.
def parserFromNonterminal (self, grammar, rule, item) : self.putLn ("self.parse_" + item.rule_name + " ()")
Pro obyčejné terminálů zkontrolujene přítomnost textu na vstupu ( a funkce check posune vstup na další lexikální symbol ).
V případě “multi-terminálů” (identifikátory, celá a desetinná čísla, řetězce v jednoduchých a dvojitých uvozovkách)
zavoláme readIdentifier, readNumber, … z lexeru
http://gitlab.fjfi.cvut.cz/culikzde/view/-/blob/master/tutorial/plain-grammar/plain_lexer.py
def parserFromTerminal (self, grammar, rule, item) : symbol = item.symbol_ref if symbol.multiterminal : func = symbol.ident if func.endswith ("_number") : func = func [ : -7 ] if func.endswith ("_literal") : func = func [ : -8 ] func = "read" + func.capitalize() self.putLn ("self." + func + " ()") else : if symbol.text != "": self.putLn ("self.check (" + '"' + symbol.text + '"' + ")")
Funkce condition má vytvořit/napsat podmínku pro zadanou množinu počátečních symbolů collection.
Podle počtu prvků množiny napíše jedno porovnání, několik or,
případně deklaruje novou konstantu (pokud již nebyla deklarována).
def condition (self, grammar, collection) : cnt = 0 for inx in range (len (collection)) : if collection [inx] : cnt = cnt + 1 if cnt == 0 : # grammar.error ("Empty set") # return "nothing" code = "True" # !? elif cnt <= 3 : code = "" start = True for inx in range (len (collection)) : if collection [inx] : if not start : code = code + " or " start = False symbol = grammar.symbols[inx] if symbol.text != "" : code = code + "self.tokenText == " + '"' + symbol.text + '"' else : code = code + "self.token == " + symbol.ident else : num = self.registerCollection (grammar, collection) code = "self.set_" + str (num) + " [self.token]"; return code
def conditionFromAlternative (self, grammar, alt) : code = self.condition (grammar, alt.first) return code
def conditionFromExpression (self, grammar, expr) : code = "" for alt in expr.alternatives : if code != "" : code = code + " or " code = code + self.conditionFromAlternative (grammar, alt) return code