Nom correct pour un analyseur de descente récursif qui utilise des boucles pour gérer la récursion gauche?

Cette grammaire est récursive:

Expression  ::= AdditionExpression

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

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

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

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

Donc, en théorie, la descente récursive ne fonctionnera pas. Mais en exploitant les propriétés de la grammaire selon lesquelles chaque règle récursive gauche correspond à un niveau de priorité spécifique et que l'anticipation d'un seul jeton suffit pour choisir la production correcte, les règles récursives gauches peuvent être analysées individuellement avec des boucles while.

Par exemple, pour analyser le non-terminal AdditionExpression, ce pseudocode suffit:

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
}

Quel est le nom correct pour ce type d'analyseur? Cet article informatif ne s'y réfère que comme la «solution classique»: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Il doit y avoir un nom propre pour ce type d'analyseur.

Il s'agit simplement d'un analyseur LL (1) implémenté avec une descente récursive.

Commence avec:

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

appliquer la suppression de la récursion à gauche pour obtenir une grammaire LL (1):

AdditionExpression  ::= 
    MultiplicationExpression AdditionExpressionTail

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

écrire les fonctions correspondantes:

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()
        }
    }
}

supprimer la récursivité de la queue:

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
        }
    }
}

en ligne:

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
        }
    }
}

et il vous suffit d'ajouter le traitement sémantique pour obtenir votre fonction.

Vous souhaitez examiner LL ($k$) analyse . L'article de Wikipedia est pour la plupart inutile, mais il s'agit essentiellement d'une descente récursive avec$k$ les symboles se regardent.

Il existe également LL ($*$), ce qui permet une anticipation illimitée.

Voir ici pour un aperçu complet de la puissance de cette classe d'analyseurs.