Einige Regeln sind nicht tatsächlich LL(1)

Obwohl die Python-Grammatik technisch gesehen eine LL(1)-Grammatik ist (weil sie von einem LL(1)-Parser analysiert wird), sind mehrere Regeln nicht LL(1) und es werden mehrere Workarounds in der Grammatik und in anderen Teilen von CPython implementiert, um damit umzugehen. Betrachten Sie zum Beispiel die Regel für Zuweisungsausdrücke

namedexpr_test: [NAME ':='] test

Diese einfache Regel ist mit der Python-Grammatik nicht kompatibel, da NAME zu den Elementen des First-Set der Regel test gehört. Um diese Einschränkung zu umgehen, ist die tatsächliche Regel, die in der aktuellen Grammatik vorkommt:

namedexpr_test: test [':=' test]

Was eine viel breitere Regel ist als die vorherige und Konstruktionen wie [x for x in y] := [1,2,3] erlaubt. Die Art und Weise, wie die Regel auf ihre gewünschte Form beschränkt wird, ist durch die Ablehnung dieser unerwünschten Konstruktionen bei der Umwandlung des Parse-Baums in den abstrakten Syntaxbaum. Dies ist nicht nur unschön, sondern auch eine beträchtliche Wartungsbelastung, da sie die AST-Erstellungsroutinen und den Compiler zwingt, in eine Situation zu geraten, in der sie wissen müssen, wie gültige von ungültigen Programmen getrennt werden, was ausschließlich die Verantwortung des Parsers sein sollte. Dies führt auch dazu, dass die aktuelle Grammatikdatei nicht korrekt widerspiegelt, was die tatsächliche Grammatik ist (d. h. die Sammlung aller gültigen Python-Programme).

Ähnliche Workarounds erscheinen in mehreren anderen Regeln der aktuellen Grammatik. Manchmal ist dieses Problem unlösbar. Zum Beispiel zeigt bpo-12782: Multiple context expressions do not support parentheses for continuation across lines, wie eine LL(1)-Regel, die das Schreiben unterstützt,

with (
    open("a_really_long_foo") as foo,
    open("a_really_long_baz") as baz,
    open("a_really_long_bar") as bar
):
  ...

nicht möglich ist, da die First-Sets der Grammatik-Elemente, die als Context Manager auftreten können, die öffnende Klammer enthalten, was die Regel mehrdeutig macht. Diese Regel ist nicht nur konsistent mit anderen Teilen der Sprache (wie der Regel für mehrere Importe), sondern auch sehr nützlich für Auto-Formatierungs-Tools, da geklammerte Gruppen normalerweise verwendet werden, um Elemente zu gruppieren, die zusammen formatiert werden sollen (auf die gleiche Weise, wie Tools mit dem Inhalt von Listen, Mengen usw. arbeiten).

Komplizierte AST-Analyse

Ein weiteres Problem des aktuellen Parsers ist die enorme Kopplung zwischen den AST-Generierungsroutinen und der spezifischen Form der erzeugten Parse-Bäume. Dies macht den Code zur Generierung des AST besonders kompliziert, da viele Aktionen und Entscheidungen implizit sind. Zum Beispiel weiß der AST-Generierungscode, welche Alternativen einer bestimmten Regel basierend auf der Anzahl der Kindknoten in einem gegebenen Parse-Knoten erzeugt werden. Dies macht den Code schwer nachvollziehbar, da diese Eigenschaft nicht direkt mit der Grammatikdatei zusammenhängt und von Implementierungsdetails beeinflusst wird. Infolgedessen muss ein erheblicher Teil des AST-Generierungscodes zur Inspektion und Analyse der spezifischen Form der Parse-Bäume verwendet werden, die er empfängt.

Fehlende Linksrekursion

Wie zuvor beschrieben, ist eine Einschränkung von LL(1)-Grammatiken, dass sie keine Linksrekursion zulassen. Dies macht das Schreiben einiger Regeln sehr unnatürlich und weit entfernt von der Art und Weise, wie Programmierer normalerweise über das Programm denken. Zum Beispiel dieser Konstrukt (eine einfachere Variation mehrerer Regeln in der aktuellen Grammatik)

expr: expr '+' term | term

kann nicht von einem LL(1)-Parser analysiert werden. Das traditionelle Gegenmittel ist, die Grammatik neu zu schreiben, um das Problem zu umgehen

expr: term ('+' term)*

Das Problem, das bei dieser Form auftritt, ist, dass der Parse-Baum eine sehr unnatürliche Form annehmen muss. Das liegt daran, dass mit dieser Regel für das Eingabeprogramm a + b + c der Parse-Baum abgeflacht wird (['a', '+', 'b', '+', 'c']) und nachbearbeitet werden muss, um einen linksrekursiven Parse-Baum zu konstruieren ([['a', '+', 'b'], '+', 'c']). Das erzwungene Schreiben der zweiten Regel führt nicht nur dazu, dass der Parse-Baum die gewünschte Assoziativität nicht korrekt widerspiegelt, sondern belastet auch spätere Kompilierungsphasen zusätzlich, um diese Fälle zu erkennen und nachzubearbeiten.

Zwischenliegender Parse-Baum

Das letzte Problem des aktuellen Parsers ist die zwischenzeitliche Erstellung eines Parse-Baums oder Concrete Syntax Tree, der später in einen Abstract Syntax Tree umgewandelt wird. Obwohl die Konstruktion eines CST in Parser- und Compiler-Pipelines sehr üblich ist, wird in CPython dieser zwischenliegende CST von nichts anderem verwendet (er wird nur indirekt über das parser-Modul offengelegt, und ein überraschend kleiner Teil des Codes bei der CST-Produktion wird im Modul wiederverwendet). Was schlimmer ist: Der gesamte Baum wird im Speicher gehalten, wobei viele Zweige, die aus Ketten von Knoten mit einem einzelnen Kind bestehen, erhalten bleiben. Dies hat sich als erheblicher Speicherverbrauch erwiesen (zum Beispiel in bpo-26415: Excessive peak memory consumption by the Python parser).

Die Notwendigkeit, ein Zwischenergebnis zwischen der Grammatik und dem AST zu erzeugen, ist nicht nur unerwünscht, sondern macht auch den AST-Generierungsschritt wesentlich komplizierter und erhöht die Wartungsbelastung erheblich.

Linksrekursion

PEG-Parser unterstützen normalerweise keine Linksrekursion, aber wir haben eine Technik implementiert, die der von Medeiros et al. [2] beschriebenen ähnelt, jedoch den Memoisations-Cache anstelle von statischen Variablen verwendet. Dieser Ansatz ist näher an dem von Warth et al. [3] beschriebenen. Dies ermöglicht es uns, nicht nur einfache linksrekursive Regeln, sondern auch komplexere Regeln zu schreiben, die indirekte Linksrekursion beinhalten, wie

rule1: rule2 | 'a'
rule2: rule3 | 'b'
rule3: rule1 | 'c'

und "versteckte Linksrekursion" wie

rule: 'optional'? rule '@' some_other_rule

Syntax

Die Grammatik besteht aus einer Sequenz von Regeln der Form

rule_name: expression

Optional kann rechts neben dem Regelnamen ein Typ angegeben werden, der den Rückgabetyp der C- oder Python-Funktion angibt, die der Regel entspricht

rule_name[return_type]: expression

Wenn der Rückgabetyp weggelassen wird, wird in C ein void * und in Python ein Any zurückgegeben.

rule_name: first_rule second_rule

rule_name[return_type]:
    | first_alt
    | second_alt

rule_name: (e)

rule_name: (e1 e2)*

rule_name: [e]

rule_name: e (',' e)* [',']

rule_name: (e1 e2)*

rule_name: (e1 e2)+

rule_name: ','.e+

primary: atom !'.' !'(' !'['

rule_name: '(' ~ some_rule ')' | some_alt

rule_name[return_type]: '(' a=some_other_rule ')' { a }

Grammatik-Aktionen

Um die Zwischenschritte zu vermeiden, die die Beziehung zwischen der Grammatik und der AST-Generierung verschleiern, erlaubt der vorgeschlagene PEG-Parser die direkte Erzeugung von AST-Knoten für eine Regel durch Grammatikaktionen. Grammatikaktionen sind sprachspezifische Ausdrücke, die ausgewertet werden, wenn eine Grammatikregel erfolgreich analysiert wurde. Diese Ausdrücke können in Python oder C geschrieben werden, abhängig von der gewünschten Ausgabe des Parser-Generators. Das bedeutet, wenn man einen Parser in Python und einen in C erzeugen möchte, müssten zwei Grammatikdateien geschrieben werden, jede mit einem anderen Satz von Aktionen, wobei alles andere als die genannten Aktionen in beiden Dateien identisch bleibt. Als Beispiel einer Grammatik mit Python-Aktionen wird der Teil des Parser-Generators, der Grammatikdateien parst, aus einer Metagrammatikdatei mit Python-Aktionen bootstrapped, die als Ergebnis des Parsens den Grammatikbaum erzeugt.

Im spezifischen Fall der neu vorgeschlagenen PEG-Grammatik für Python erlauben Aktionen die direkte Beschreibung, wie der AST in der Grammatik selbst zusammengesetzt wird, was ihn klarer und wartungsfreundlicher macht. Dieser AST-Generierungsprozess wird durch die Verwendung einiger Hilfsfunktionen unterstützt, die gemeinsame AST-Objektmanipulationen und andere erforderliche Operationen, die nicht direkt mit der Grammatik zusammenhängen, auslagern.

Um diese Aktionen anzugeben, kann jede Alternative durch den Aktionscode in geschweiften Klammern gefolgt werden, der den Rückgabewert der Alternative angibt

rule_name[return_type]:
    | first_alt1 first_alt2 { first_alt1 }
    | second_alt1 second_alt2 { second_alt1 }

Wenn die Aktion weggelassen wird und C-Code generiert wird, gibt es zwei verschiedene Möglichkeiten

1. Wenn es einen einzelnen Namen in der Alternative gibt, wird dieser zurückgegeben.
2. Wenn nicht, wird ein Dummy-Name-Objekt zurückgegeben (dieser Fall sollte vermieden werden).

Wenn die Aktion weggelassen wird und Python-Code generiert wird, wird eine Liste mit allen analysierten Ausdrücken zurückgegeben (dies ist für Debugging gedacht).

Die vollständige Metagrammatik für die vom PEG-Generator unterstützten Grammatiken ist

start[Grammar]: grammar ENDMARKER { grammar }

grammar[Grammar]:
    | metas rules { Grammar(rules, metas) }
    | rules { Grammar(rules, []) }

metas[MetaList]:
    | meta metas { [meta] + metas }
    | meta { [meta] }

meta[MetaTuple]:
    | "@" NAME NEWLINE { (name.string, None) }
    | "@" a=NAME b=NAME NEWLINE { (a.string, b.string) }
    | "@" NAME STRING NEWLINE { (name.string, literal_eval(string.string)) }

rules[RuleList]:
    | rule rules { [rule] + rules }
    | rule { [rule] }

rule[Rule]:
    | rulename ":" alts NEWLINE INDENT more_alts DEDENT {
          Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts)) }
    | rulename ":" NEWLINE INDENT more_alts DEDENT { Rule(rulename[0], rulename[1], more_alts) }
    | rulename ":" alts NEWLINE { Rule(rulename[0], rulename[1], alts) }

rulename[RuleName]:
    | NAME '[' type=NAME '*' ']' {(name.string, type.string+"*")}
    | NAME '[' type=NAME ']' {(name.string, type.string)}
    | NAME {(name.string, None)}

alts[Rhs]:
    | alt "|" alts { Rhs([alt] + alts.alts)}
    | alt { Rhs([alt]) }

more_alts[Rhs]:
    | "|" alts NEWLINE more_alts { Rhs(alts.alts + more_alts.alts) }
    | "|" alts NEWLINE { Rhs(alts.alts) }

alt[Alt]:
    | items '$' action { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=action) }
    | items '$' { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=None) }
    | items action { Alt(items, action=action) }
    | items { Alt(items, action=None) }

items[NamedItemList]:
    | named_item items { [named_item] + items }
    | named_item { [named_item] }

named_item[NamedItem]:
    | NAME '=' ~ item {NamedItem(name.string, item)}
    | item {NamedItem(None, item)}
    | it=lookahead {NamedItem(None, it)}

lookahead[LookaheadOrCut]:
    | '&' ~ atom {PositiveLookahead(atom)}
    | '!' ~ atom {NegativeLookahead(atom)}
    | '~' {Cut()}

item[Item]:
    | '[' ~ alts ']' {Opt(alts)}
    |  atom '?' {Opt(atom)}
    |  atom '*' {Repeat0(atom)}
    |  atom '+' {Repeat1(atom)}
    |  sep=atom '.' node=atom '+' {Gather(sep, node)}
    |  atom {atom}

atom[Plain]:
    | '(' ~ alts ')' {Group(alts)}
    | NAME {NameLeaf(name.string) }
    | STRING {StringLeaf(string.string)}

# Mini-grammar for the actions

action[str]: "{" ~ target_atoms "}" { target_atoms }

target_atoms[str]:
    | target_atom target_atoms { target_atom + " " + target_atoms }
    | target_atom { target_atom }

target_atom[str]:
    | "{" ~ target_atoms "}" { "{" + target_atoms + "}" }
    | NAME { name.string }
    | NUMBER { number.string }
    | STRING { string.string }
    | "?" { "?" }
    | ":" { ":" }

Als illustratives Beispiel erlaubt diese einfache Grammatikdatei die direkte Generierung eines vollständigen Parsers, der einfache arithmetische Ausdrücke analysieren kann und einen gültigen C-basierten Python-AST zurückgibt

start[mod_ty]: a=expr_stmt* $ { Module(a, NULL, p->arena) }
expr_stmt[stmt_ty]: a=expr NEWLINE { _Py_Expr(a, EXTRA) }
expr[expr_ty]:
    | l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA) }
    | l=expr '-' r=term { _Py_BinOp(l, Sub, r, EXTRA) }
    | t=term { t }

term[expr_ty]:
    | l=term '*' r=factor { _Py_BinOp(l, Mult, r, EXTRA) }
    | l=term '/' r=factor { _Py_BinOp(l, Div, r, EXTRA) }
    | f=factor { f }

factor[expr_ty]:
    | '(' e=expr ')' { e }
    | a=atom { a }

atom[expr_ty]:
    | n=NAME { n }
    | n=NUMBER { n }
    | s=STRING { s }

Hier ist EXTRA ein Makro, das zu start_lineno, start_col_offset, end_lineno, end_col_offset, p->arena expandiert, dies sind Variablen, die automatisch vom Parser injiziert werden; p zeigt auf ein Objekt, das den Zustand für den Parser verwaltet.

Eine ähnliche Grammatik, die für die Erzeugung von Python-AST-Objekten geschrieben wurde

start: expr NEWLINE? ENDMARKER { ast.Expression(expr) }
expr:
    | expr '+' term { ast.BinOp(expr, ast.Add(), term) }
    | expr '-' term { ast.BinOp(expr, ast.Sub(), term) }
    | term { term }

term:
    | l=term '*' r=factor { ast.BinOp(l, ast.Mult(), r) }
    | term '/' factor { ast.BinOp(term, ast.Div(), factor) }
    | factor { factor }

factor:
    | '(' expr ')' { expr }
    | atom { atom }

atom:
    | NAME { ast.Name(id=name.string, ctx=ast.Load()) }
    | NUMBER { ast.Constant(value=ast.literal_eval(number.string)) }

Validierung

Um mit der Validierung zu beginnen, kompilieren wir regelmäßig die gesamte Python 3.8 Standardbibliothek und vergleichen jeden Aspekt des resultierenden AST mit dem, der vom Standardcompiler erzeugt wurde. (Dabei haben wir ein paar Fehler in der Behandlung von Zeilen- und Spaltennummern durch den Standard-Parser gefunden, die wir alle über eine Reihe von Issues und PRs upstream behoben haben.)

Wir haben auch gelegentlich eine viel größere Codebasis (die ca. 3800 beliebtesten Pakete auf PyPI) kompiliert und dies hat uns geholfen, ein paar (sehr wenige) zusätzliche Fehler im neuen Parser zu finden.

(Ein Bereich, den wir nicht ausgiebig untersucht haben, ist die Ablehnung aller falschen Programme. Wir haben Unit-Tests, die eine bestimmte Anzahl von expliziten Ablehnungen überprüfen, aber es könnte mehr Arbeit geleistet werden, z.B. durch die Verwendung eines Fuzzers, der zufällige subtile Fehler in bestehenden Code einfügt. Wir sind offen für Hilfe in diesem Bereich.)

Performance

Wir haben die Leistung des neuen Parsers so optimiert, dass er sowohl in Geschwindigkeit als auch im Speicherverbrauch innerhalb von 10 % des aktuellen Parsers liegt. Während der PEG/Packrat-Parsing-Algorithmus naturgemäß mehr Speicher verbraucht als der aktuelle LL(1)-Parser, haben wir einen Vorteil, da wir kein separates CST erstellen.

Unten sind einige Benchmarks. Diese konzentrieren sich auf die Kompilierung von Quellcode in Bytecode, da dies die realistischste Situation ist. Die Rückgabe eines AST an Python-Code ist nicht so repräsentativ, da der Prozess der Konvertierung des internen AST (nur für C-Code zugänglich) in einen externen AST (eine Instanz von ast.AST) mehr Zeit benötigt als der Parser selbst.

Alle hier berichteten Messungen wurden auf einem aktuellen MacBook Pro durchgeführt, wobei der Median von drei Läufen genommen wurde. Es wurden keine besonderen Vorkehrungen getroffen, um andere laufende Anwendungen auf demselben Rechner zu stoppen.

Die ersten Zeitmessungen sind für unsere kanonische Testdatei, die 100.000 Zeilen enthält, die endlos die folgenden drei Zeilen wiederholen

1 + 2 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + ((((((11 * 12 * 13 * 14 * 15 + 16 * 17 + 18 * 19 * 20))))))
2*3 + 4*5*6
12 + (2 * 3 * 4 * 5 + 6 + 7 * 8)

• Nur das Parsen und Wegwerfen des internen AST dauert 1,16 Sekunden bei einer maximalen RSS von 681 MiB.
• Das Parsen und Konvertieren in ast.AST dauert 6,34 Sekunden, maximale RSS 1029 MiB.
• Das Parsen und Kompilieren in Bytecode dauert 1,28 Sekunden, maximale RSS 681 MiB.
• Mit dem aktuellen Parser dauert das Parsen und Kompilieren 1,44 Sekunden, maximale RSS 836 MiB.

Für diese spezielle Testdatei ist der neue Parser schneller und verbraucht weniger Speicher als der aktuelle Parser (vergleichen Sie die letzten beiden Punkte).

Wir haben auch Zeitmessungen mit einer realistischeren Nutzlast durchgeführt, der gesamten Python 3.8 Standardbibliothek. Diese Nutzlast besteht aus 1.641 Dateien, 749.570 Zeilen, 27.622.497 Bytes. (Obwohl 11 Dateien aufgrund von Kodierungsproblemen, manchmal absichtlich, von keinem Python 3-Parser kompiliert werden können.)

• Das Kompilieren und Wegwerfen des internen AST dauerte 2,141 Sekunden. Das sind 350.040 Zeilen/Sekunde oder 12.899.367 Bytes/Sekunde. Die maximale RSS betrug 74 MiB (die größte Datei in der Standardbibliothek ist viel kleiner als unsere kanonische Testdatei).
• Das Kompilieren in Bytecode dauerte 3,290 Sekunden. Das sind 227.861 Zeilen/Sekunde oder 8.396.942 Bytes/Sekunde. Maximale RSS 77 MiB.
• Das Kompilieren in Bytecode mit dem aktuellen Parser dauerte 3,367 Sekunden. Das sind 222.620 Zeilen/Sekunde oder 8.203.780 Bytes/Sekunde. Maximale RSS 70 MiB.

Beim Vergleich der letzten beiden Punkte stellen wir fest, dass der neue Parser geringfügig schneller ist, aber geringfügig (ca. 10 %) mehr Speicher verbraucht. Wir glauben, dass dies akzeptabel ist. (Außerdem gibt es wahrscheinlich noch ein paar Optimierungen, die wir vornehmen können, um den Speicherverbrauch zu reduzieren.)