Richtiger Name für einen rekursiven Abstiegsparser, der Schleifen verwendet, um die linke Rekursion zu behandeln?

Diese Grammatik bleibt rekursiv:

Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

Theoretisch funktioniert ein rekursiver Abstieg also nicht. Durch Ausnutzen der Eigenschaften der Grammatik, dass jede linksrekursive Regel einer bestimmten Prioritätsebene entspricht und der Lookahead eines einzelnen Tokens ausreicht, um die richtige Produktion auszuwählen, können die linksrekursiven Regeln einzeln mit while-Schleifen analysiert werden.

Um beispielsweise das nicht-terminale AdditionExpression zu analysieren, reicht dieser Pseudocode aus:

function parse_addition_expression() {
    num = parse_multiplication_expression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            num += parse_multiplication_expression()
        else if (current_token == MINUS)
            num -= parse_multiplication_expression()
        else {
            unget_token()
            return num
        }
    }
    return num
}

Wie lautet der richtige Name für diesen Parsertyp? In diesem informativen Artikel wird es nur als "klassische Lösung" bezeichnet: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Für diesen Parsertyp muss ein Eigenname vorhanden sein.

Es ist nur ein LL (1) -Parser, der mit rekursivem Abstieg implementiert ist.

Beginnt mit:

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

gelten links Beseitigung der Rekursion eine LL (1) Grammatik zu erhalten:

AdditionExpression  ::= 
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

Schreiben Sie die entsprechenden Funktionen:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    parse_AdditionExpressionTail()
}

function parse_AdditionExpressionTail() {
    if (has_token()) {
        get_token()
        if (current_token == PLUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else if (current_token == MINUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else {
            unget_token()
        }
    }
}

Schwanzrekursion entfernen:

function parse_AdditionExpressionTail() {
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

in der Reihe:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

und Sie müssen nur die semantische Verarbeitung hinzufügen, um Ihre Funktion zu erhalten.

$k$$k$

$*$

Sehen Sie hier für einen umfassenden Überblick darüber , wie mächtig diese Klasse von Parsern ist.