class: center, middle ## [Arpeggio parser](/courses/#table-of-contents) .author[[Milovan TomaÅ”eviÄ, Ph.D.](https://www.milovantomasevic.com/)] .small[.medium[[šā milovantomasevic.com](https://milovantomasevic.com)</br> [āā tomas.ftn.e2@gmail.com](mailto:tomas.ftn.e2@gmail.com)]] .created[25.05.2020 u 23:10] --- class: split-20 nopadding background-image: url(../key.jpg) .column_t2.center[.vmiddle[ .fgtransparent[  ] ]] .column_t2[.vmiddle.nopadding[ .shadelight[.boxtitle1[ .small[ ## Acknowledgements #### University of Novi Sad | Serbia - [Igor DejanoviÄ, Ph.D., Associate Professor](http://igordejanovic.net/) - [Faculty of Technical Sciences](http://ftn.uns.ac.rs/) - [Chair of Informatics](http://informatika.ftn.uns.ac.rs/) ]]] ]] .footer.small[ - #### Slides are created according to sources in the literature & Acknowledgements ] --- name: sadrzaj # Sadržaj - [Kratak pregled Python parsera](#pregled) - [Arpeggio - uvod](#arpeggio) - [Konfiguracija parsera](#konfiguracija-parsera) - [Debagovanje, vizualizacija](#debagovanje) - [Analiza stabala parsiranja](#analiza) --- name: pregled class: center, middle, inverse # PyParsing --- layout: true .section[[Kratak pregled Python parsera](#sadrzaj)] --- ## PyParsing - 100% Python - MIT licenca - PEG parser - Gramatika se zadaje Python izrazima preko redefinisanih operatora `+` i `|` - Mane - Slabija podrÅ”ka za semantiÄku analizu - Referenciranje pravila unapred - `Forward` - Nije moguÄe definisati gramatiku putem PEG notacije - http://pyparsing.wikispaces.com/ --- ## Primer ```python from pyparsing import Word, alphas greet = Word( alphas ) + "," + Word( alphas ) + "!" # <-- grammar hello = "Hello, World!" print (hello, "->", greet.parseString( hello )) ``` ``` Hello, World! -> ['Hello', ',', 'World', '!'] ``` --- ## parsimonious - 100% Python - https://github.com/erikrose/parsimonious - PEG (packrat) parser - MIT licenca - Cilj - performanse - Gramatika se zadaje tekstualnim jezikom. - *Whitespace* karakteri se zadaju gramatikom. --- ## Primer ```python >>> from parsimonious.grammar import Grammar >>> grammar = Grammar( ... """ ... bold_text = bold_open text bold_close ... text = ~"[A-Z 0-9]*"i ... bold_open = "((" ... bold_close = "))" ... """) >>> print grammar.parse('((bold stuff))') <Node called "bold_text" matching "((bold stuff))"> <Node called "bold_open" matching "(("> <RegexNode called "text" matching "bold stuff"> <Node called "bold_close" matching "))"> ``` --- ## PLY - 100% Python - LR parser - Inspirisan sa lex/yacc alatima - Pravila prioriteta, oporavak od greÅ”aka, podrÅ”ka za neodreÄene gramatike. - Tokenizacija kao poseban korak (lex modul) - Gramatika se piÅ”e u docstring-ovima za semantiÄke akcije. --- ## Primer ```python # When parsing starts, try to make a "chemical_equation" because it's # the name on left-hand side of the first p_* function definition. def p_species_list(p): "chemical_equation : chemical_equation species" p[0] = p[1] + [p[2]] def p_species(p): "chemical_equation : species" p[0] = [p[1]] ``` --- name: arpeggio class: center, middle, inverse layout: false # Arpeggio --- layout: true .section[[Arpeggio](#sadrzaj)] --- ## Osnovne osobine - 100% Python kod - MIT licenca - Definisanje gramatike putem Python izraza ili putem PEG notacije - Puna podrÅ”ka za semantiÄku analizu - Dobra podrÅ”ka za debagovanje - Vizualizacija stabla parsiranja i modela parsera upotrebom GraphViz biblioteke. - Dobra prijava greÅ”aka - MoguÄnost viÅ”estruke analize istog stabla parsiranja - https://github.com/igordejanovic/arpeggio/ ---  --- ## PEG pravila - Gramatika se zadaje skupom PEG pravila - Svako pravilo definiÅ”e naÄin prepoznavanja odreÄenog (ne)terminala na ulazu. --- ## PEG pravila (2) Ako su e, e1 i e2 PEG pravila definisani su sledeÄi elementarni PEG izrazi: - *Sekvenca:* `e1 e2` - izraz Äe dovesti do prepoznavanja ulaza ako i samo ako redom izrazi `e1` i `e2` prepoznaju ulaz - *UreÄeni izbor:* `e1 / e2` - izraz Äe biti prepoznat ukoliko bilo izraz `e1` ili izraz `e2` dovedu do prepoznavanja u navedenom redosledu (prvo `e1` pa zatim `e2` ) - *Jedan ili viÅ”e:* `e+` - sukcesivno se vrÅ”i prepoznavanje izraza `e` dok god uspeva. Ukoliko je `e` prepoznat bar jednom prepoznavanje je uspeÅ”no - *Nula ili viÅ”e:* `e*` - sukcesivno se vrÅ”i prepoznavanje izraza `e` dok god uspeva. Izraz uvek uspeva pri Äemu ako izraz `e` nije prepoznat ni jednom rezultat je prazan string, - *Opciono:* `e?` - izraz uvek uspeva. Ukoliko se prepozna string sa ulaza biÄe konzumiran. --- ## PEG pravila - predikati Predikati su pravila koja prepoznaju string sa ulaza ali ga ne konzumiraju. - *"I" predikat:* `&e` - pravilo je uspeÅ”no samo ukoliko je `e` prepoznato na ulazu. - *"Ne" predikat:* `!e` - pravilo je uspeÅ”no samo ukoliko `e` nije prepoznato na ulazu. --- ## Koncepti - *Parser model* - opisuje odreÄenu vrstu dijagrama stanja-prelaza parsera. Može se vizualizovati upotrebom dot alata u cilju debagovanja. - *Stablo parsiranja* - može se vizualizovati dot alatom - *SemantiÄke akcije* - transformiÅ”u stablo parsiranja u drugi oblik upotrebom *Visitor* obrasca. --- ## Definisanje gramatike - interni DSL .lcol-wide2[ ```python def program(): return Kwd('begin'), ZeroOrMore(command), Kwd('end'), EOF def command(): return [up, down, left, right] def up(): return 'up' def down(): return 'down' def left(): return 'left' def right(): return 'right' ``` ] .rcol-narrow2[ ``` begin up up left down right end ``` ] - GramatiÄka pravila ā Python funkcije - Sekvenca ā n-torka (*tuple*) - UreÄeni izbor ā Python lista - Ostalo ā instance klasa (npr. `ZeroOrMore, OneOrMore, Optional`) - Navedena gramatika prepoznaje ulaz dat na desnoj strani. --- ## Definisanje gramatike - eksterni DSL ``` program = 'begin' command* 'end' EOF command = UP/DOWN/LEFT/RIGHT UP = 'up' DOWN = 'down' LEFT = 'left' RIGHT = 'right' ``` --- ## Instanciranje parsera ```python from arpeggio import ParserPython def program():... parser = ParserPython(program) # Ili za eksternu PEG notaciju from arpeggio.cleanpeg import ParserPEG parser = ParserPEG(grammar) # gde je grammar gramatika u PEG notaciji ``` --- ## Model parsera  ``` from arpeggio import ParserPython ... parser = ParserPython(robot, debug=True) ``` --- ## Stablo parsiranja ```python prog_src = """ begin up up left down right end """ parse_tree = parser.parse(prog_src) ```  .center[Elementi stabla su terminali i neterminali.] [Dokumentacija: Stablo parsiranja, navigacija, terminali i ne-terminali](http://igordejanovic.net/Arpeggio/parse_trees/) --- ## Terminali (*Terminal nodes*) - Kreiraju se pravilima koje nasleÄuju `Match` pravilo. Mogu se konvertovati u string predstavu pozivom `str` funkcije. - Trenutno postoje dve `Match` naslednice: `StrMatch` i `RegExMatch`. --- ## Ne-terminali (*Non-terminal nodes*) - Kreiraju se svim ostalim pravilima: `Sequence`, `OrderedChoice`, `ZeroOrMore` itd. - NasleÄuju `list` tako da se mogu koristiti u svim kontekstima gde se može koristiti i lista. --- ## Stablo parsiranja aritmetiÄkog izraza  --- ## Informacije sadržane u Ävorovima stabla parsiranja Svaki Ävor stabla je objekat koji poseduje sledeÄe atribute: - `rule` - veze prema `ParsingExpression` naslednici iz modela parsera, odnosno pravilo koje je prepoznalo ovaj element u ulaznom stringu, - `rule_name` - ime pravila - `position` - apsolutna pozicija unutar ulaznog stringa od poÄetka. Red i kolona se može dobiti preko parsera na sledeÄi naÄin: ```python line, col = parser.pos_to_linecol(node.position) ``` --- ## Navigacija - Ne-terminali nasleÄuju `list` tako da se mogu koristiti u svim kontekstima gde se može koristiti i lista. - Indeksni pristup: ``` child = pt_node[2] ``` - Iteracija: ``` for child in pt_node: ... ``` --- ## Navigacija Dodatno se *child* elementima može pristupati i po nazivu pravila: .medium[ ```python # Grammar def foo(): return "a", bar, "b", baz, "c", ZeroOrMore(bar) def bar(): return "bar" def baz(): return "baz" # Parsing parser = ParserPython(foo) result = parser.parse("a bar b baz c bar bar bar") # Accessing parse tree nodes. All asserts will pass. # Index access assert result[1].rule_name == 'bar' # Access by rule name assert result.bar.rule_name == 'bar' # There are 8 children nodes of the root 'result' node. # Each child is a terminal in this case. assert len(result) == 8 # There is 4 bar matched from result (at the beginning and from ZeroOrMore) # Dot access collect all NTs from the given path assert len(result.bar) == 4 # You could call dot access recursively, e.g. result.bar.baz if the # rule bar called baz. In that case all bars would be collected from # the root and for each bar all baz will be collected. # Verify position # First 'bar' is at position 2 and second is at position 14 assert result.bar[0].position == 2 assert result.bar[1].position == 14 ``` ] --- name: konfiguracija-parsera class: center, middle, inverse layout: false # Konfiguracija parsera --- layout: true .section[[Konfiguracija parsera](#sadrzaj)] --- ## Osetljivost na veliÄinu slova (*Case-sensitiviy*) - Parser je podrazumevano osetljiv na veliÄinu slova. - Da se ovo promeni: ```python parser = ParserPython(calc, ignore_case=True) ``` --- ## Upravljanje "praznim" karakterima (*Whitespaces*) - Arpeggio podrazumevano preskaÄe prazne karaktere. - Da bi se ovo promenilo: ```python parser = ParserPython(calc, skipws=False) ``` - Pod praznim karakterima podrazumevaju se `\n\t\r `. Ovo se može promeniti parametrom `ws` pri konstrukciji: ```python parser = ParserPython(calc, ws='\t\r ') ``` - Ovo se može koristiti i na nivou sekvence: ```python def grammar(): return Sequence("one", "two", "three", skipws=False), "four" parser = ParserPython(grammar) pt = parser.parse('onetwothree four') ``` --- ## KljuÄne reÄi Ukoliko se ukljuÄi parametar `autokwd` tada Äe prepoznavanje svega Å”to je oblika kljuÄne reÄi biti sa uzimanjem u obzir granice reÄi (*word boundary*) odnosno kljuÄne reÄi u sklopu veÄih reÄi neÄe biti prepoznate kao takve. Primer: ``` def grammar(): return "one", "two", "three" parser = ParserPython(grammar, autokwd=True) # If autokwd is enabled this should parse without error. parser.parse("one two three") # But this will not parse as the match is done using word boundaries # so this is considered a one word. parser.parse("onetwothree") ``` --- ## Komentari Arpeggio može opciono da primi i gramatiku za komentare. Ova gramatika Äe se koristiti izmeÄu svaka dva elementarna prepoznavanja osnovne gramatike (sliÄno kao za prazne karaktere). ```python # Grammar def simpleLanguage(): return function def parameterlist(): return "(", symbol, ZeroOrMore(",", symbol), ")" def functioncall(): return symbol, "(", expressionlist, ")" def function(): return Kwd("function"), symbol, parameterlist, block ... def comment(): return [_("//.*"), _("/\*.*\*/")] parser = ParserPython(simpleLanguage, comment) ``` --- ## Redukcija stabala parsiranja Kod "dubokih" gramatika Äesto imamo pojavu ne-terminala sa samo jednim podÄvorom. Zbog jednostavnosti analize nekada je poželjno eliminisati takve Ävorove iz stabla. ```python parser = ParserPython(calc, reduce_tree=True) ```  --- ## Parsiranje do kraja linije Nekada je potrebno da pravila koja nasleÄuju `Repetition` (`ZeroOrMore` i `OneOrMore`) vrÅ”e parsiranje samo do kraja linije. ```python def grammar(): return first, second def first(): return ZeroOrMore(["a", "b"], eolterm=True) def second(): return "a" # first rule should match only first line # so that second rule will match "a" on the new line input = """a a b a b b a""" parser = ParserPython(grammar) result = parser.parse(input) ``` --- name: debagovanje class: center, middle, inverse layout: false # Debagovanje i vizualizacija --- layout: true .section[[Debagovanje](#sadrzaj)] --- ## Debagovanje (*Debugging*) Arpeggio se može postaviti da radi u režimu za degabovanje. ```python parser = ParserPython(calc, debug=True) ``` ``` >> Entering rule calc=Sequence at position 0 => *-(4-1)*5+( >> Entering rule OneOrMore in calc at position 0 => *-(4-1)*5+( >> Entering rule expression=Sequence in calc at position 0 => *-(4-1)*5+( >> Entering rule term=Sequence in expression at position 0 => *-(4-1)*5+( >> Entering rule factor=Sequence in term at position 0 => *-(4-1)*5+( >> Entering rule Optional in factor at position 0 => *-(4-1)*5+( >> Entering rule OrderedChoice in factor at position 0 => *-(4-1)*5+( >> Match rule StrMatch(+) in factor at position 0 => *-(4-1)*5+( -- No match '+' at 0 => '*-*(4-1)*5+(' >> Match rule StrMatch(-) in factor at position 0 => *-(4-1)*5+( ++ Match '-' at 0 => '*-*(4-1)*5+(' << Leaving rule OrderedChoice << Leaving rule Optional >> Entering rule OrderedChoice in factor at position 1 => -*(4-1)*5+(2 ``` --- ## Vizuelizacija .medium[ - U režimu za debagovanje kreiraju se `dot` fajlovi i za model parsera i za stablo parsiranja (ako nema sintaksnih greÅ”aka). - Koristimo `dot` alat (deo GraphViz alata) za konverziju u grafiÄke formate. ``` $ dot -Tpng -O calc_parser_model.dot ``` ]  --- ## Obrada greÅ”aka pri parsiranju ```python parser = ParserPython(calc) # 'r' in the following expression can't be recognized by # calc grammar input_expr = "23+4/r-89" parse_tree = parser.parse(input_expr) ``` ``` Traceback (most recent call last): ... arpeggio.NoMatch: Expected '+' or '-' or 'number' or '(' at position (1, 6) => '23+4/*r-89'. ``` - `NoMatch` izuzetak. - `rules` - lista pravila (iz modela parsera) koja su pokuÅ”ana na datom mestu. - `position` - apsolutna pozicija od poÄetka fajla - `line`, `col` - red i kolona - `parser` - referenca na parser objekat --- name: analiza class: center, middle, inverse layout: false # Analiza stabala parsiranja --- layout: true .section[[Analiza](#sadrzaj)] --- ## SemantiÄke akcije - transformacija u AST ```python from arpeggio ParserPython, visit_parse_tree parser = ParserPython(calc) input_expr = "-(4-1)*5+(2+4.67)+5.89/(.2+7)" parse_tree = parser.parse(input_expr) result = visit_parse_tree(parse_tree, CalcVisitor()) ``` --- ## SemantiÄke akcije - transformacija u AST (2) ```python class CalcVisitor(PTNodeVisitor): def visit_number(self, node, children): """ Converts node value to float. """ if self.debug: print("Converting {}.".format(node.value)) return float(node.value) def visit_factor(self, node, children): """ Applies a sign to the expression or number. """ if self.debug: print("Factor {}".format(children)) if len(children) == 1: return children[0] sign = -1 if children[0] == '-' else 1 return sign * children[-1] ``` --- ## `SemanticActionResults` - Klasa Äija instanca se dobija kao `children` parametar u akcijama. - Enkapsulira rezultate vraÄene od akcija nižeg nivoa. - NasleÄuje Python listu. ```python def visit_bar(self, node, children): # Index access child = children[2] # Iteration for child in children: ... # Rule name lookup # Returns a list of all rules created by PEG rule 'baz' baz_created = children['baz'] ``` --- ## Postprocesiranje u drugom pozivu - Nekada se konstrukcija AST-a mora obaviti u dva prolaza (npr. razreÅ”avanje referenci). - Opciona metoda oblika `second_<rule_name>`. Dobija objekat koji vraÄa poziv `visit_<rule_name>` i dodatno ga obraÄuje. --- ## Podrazumevane semantiÄke akcije .medium[ - Ako nije definisana metoda `visit_<rule_name>` Arpeggio Äe primeniti podrazumevanu akciju Äija logika je sledeÄa: - Ako je Ävor kreiran `StrMatch` pravilom (string literal) vraÄa se `None` Äime se Ävor eliminiÅ”e iz `children` kolekcije Ävora viÅ”eg nivoa. - Ako je krairan sa `RegExMatch` biÄe vraÄen string. - Ako je Ävor ne-terminal sa samo jednim podÄvorom biÄe vraÄen podÄvor. - Podrazumevane akcije se mogu iskljuÄiti parametrom `defaults`: ```python result = visit_parse_tree(parse_tree, CalcVisitor(defaults=False)) ``` - Podrazumevane akcije se mogu eksplicitno pozvati: ```python def visitor_myrule(self, node, children): if some_condition: ... else: return super(MyVisitor, self).visit__default__(node, children) ``` ] --- ## Primeri - [CSV](http://arpeggio.readthedocs.io/en/latest/tutorials/csv/) - [BibTeX](http://arpeggio.readthedocs.io/en/latest/tutorials/bibtex/) - [Calc](http://arpeggio.readthedocs.io/en/latest/tutorials/calc/) --- # Arpeggio dokumentacija - http://igordejanovic.net/Arpeggio/ --- class: center, middle, inverse layout: false # VeÄe džeza i slobodnih formi - improvizacije -- class: center, middle, theend, hide-text layout: false background-image: url(../theend.gif)
error:
Content is protected !!