Programming Language Parser (in Java) - Quale sarebbe un'alternativa di design migliore per un caso speciale?

Il parser predittivo selezionato (LL (k)) significa che dovrai risolvere i problemi di ricorsione a sinistra. Algoritmo per la risoluzione delle ricorsioni dirette e indirette è chiaramente descritto su wikipedia:

link

Alcune informazioni possono essere trovate nei post qui su StackOverflow:

link link link

In linguaggio umano (non scientifico :) "problema di ricorsione a sinistra" significa che non puoi ricorrere all'infinito in ricorsione con non-terminale (A - > Ab) ancora e ancora. Ad un certo punto devi alimentare l'algoritmo del parser con un terminale per interrompere un loop.

In BNF questo potrebbe essere:

Problema di ricorsione:

NT: NT T
NT: T

Una soluzione:

NT: T NT2
NT2: T NT2
NT2: 

Per la tua grammatica potrebbe essere:

DataType:
    PrimitiveDataType ArrayDimensions
 |  ComplexDataType ArrayDimensions

ArrayDimensions:
    [] ArrayDimensions
 |

Se il tuo generatore di parser non consente produzioni vuote e / o se desideri elaborare separatamente i tipi di array, prova qualcosa del tipo:

DataType:
    DataTypeName
 |  ArrayDataType

ArrayDataType:
    DataTypeName ArrayDimensions

DataTypeName:
    PrimitiveDataType
 |  ComplexDataType

ArrayDimensions:
    []
 |  [] ArrayDimensions

Il problema è che l'utilizzo di un LL (1) parser può portare alla ricorsione a sinistra . Puoi evitarlo passando a un parser LR o usando questa grammatica per evitare la ricorsione:

DataType:
    PrimitiveDataType ArrayDataType
 |  ComplexDataType ArrayDataType

ArrayDataType:
    [] ArrayDataType
 |  (empty)

Se l'analisi non fa parte del tuo progetto, cerca solo una libreria / generatore di analisi, probabilmente ce ne sono molti là fuori.

La chiave qui è semplicemente usare un parser LR piuttosto che LL. C'è una ragione per cui virtualmente nessuna implementazione usa effettivamente LL come è stato detto, ed è perché in realtà non riesce a riconoscere molte grammatiche particolarmente utili.

Questo problema che stai affrontando sembra con qualcosa che ho già affrontato. In tal caso, dovrebbe essere implementato nella classe Syntatic Analyzer e sì, genererà un albero, sarebbe effettivamente ricorsivo.

E.g.: nel mio caso, ho dovuto implementare un modo in cui la funzione avrebbe ricevuto un elenco di argomenti, quindi la mia regola di grammatica per l'elenco di argomenti sarebbe simile a questa:

<ArgLi> ::= <Arg> <ArgLi> |

dove:

<Arg> ::= '(' <Type> Identifier ')'

<ArgLi> è chiamato recursivelly

<Type> ::= 'int' | 'real' | 'str'

Identifier = {ID Head}{ID Tail}*

Quindi, per implementare questa funzione, il comando ha dei delimitatori, quindi, anche se entra in un ciclo, controllerà la regola e determinerà l'azione in base al token corrente che sto cercando.

Ad esempio, supponiamo di voler scrivere questo:

( def main [ ( int a1 ) ( str a2 )  ]

...

)

Il codice che segue la mia lingua per capire questo è:

/**
 * <Def> ::= '(' 'def' Identifier '[' <ArgLi> ']' <CommandLi> ')'
 */
public Node Def() {

    Node node = new Node(NodeIdentifier.DEF);
    if (token.getImage().equals("(")) {
        node.addSon(new Node(NodeIdentifier.TOKEN, token));
        token = readToken();
        if (token.getImage().equals("def")) {
            node.addSon(new Node(NodeIdentifier.TOKEN, token));
            token = readToken();
            if (token._getClass().equals("ID")
                    || token.getImage().equals("main")) {
                node.addSon(new Node(NodeIdentifier.TOKEN, token));
                token = readToken();
                if (token.getImage().equals("[")) {
                    node.addSon(new Node(NodeIdentifier.TOKEN, token));
                    token = readToken();
                    node.addSon(argLi());
                    if (token.getImage().equals("]")) {
                        node.addSon(new Node(NodeIdentifier.TOKEN, token));
                        token = readToken();
                        node.addSon(commandLi());
                        if (token.getImage().equals(")")) {
                            node.addSon(new Node(NodeIdentifier.TOKEN,
                                    token));
                            token = readToken();
                        } else {
                            errors.add("Error: token ')' not recognized. line: "
                                    + token.getLine());
                        }
                    } else {
                        errors.add("Error: token ']' not recognized. line: "
                                + token.getLine());
                    }
                } else {
                    errors.add("Error: token '[' not recognized. line: "
                            + token.getLine());
                }
            } else {
                errors.add("Error: token 'ID' not recognized. line: "
                        + token.getLine());
            }
        } else {
            errors.add("Error: token 'def' not recognized. line: "
                    + token.getLine());
        }
    } else {
        errors.add("Error: token '(' not recognized. line: "
                + token.getLine());
    }
    return node;
}

/**
 * <ArgLi> ::= <Arg> <ArgLi> |
 */
public Node argLi() {

    Node node = new Node(NodeIdentifier.ARGLI);
    if (token.getImage().equals("(")) {
        node.addSon(arg());
        node.addSon(argLi());
    }
    return node;
}

/**
 * <Arg> ::= '(' <Type> Identifier ')'
 */
public Node arg() {
    Node node = new Node(NodeIdentifier.ARG);
    if (token.getImage().equals("(")) {
        node.addSon(new Node(NodeIdentifier.TOKEN, token));
        token = readToken();
        node.addSon(type());
        if (token._getClass().equals("ID")) {
            node.addSon(new Node(NodeIdentifier.TOKEN, token));
            token = readToken();
            if (token.getImage().equals(")")) {
                node.addSon(new Node(NodeIdentifier.TOKEN, token));
                token = readToken();
            } else {
                errors.add("Error: token ')' not recognized. line: "
                        + token.getLine());
            }
        } else {
            errors.add("Error: token 'ID' not recognized. line: "
                    + token.getLine());
        }
    } else {
        errors.add("Error: token '(' not recognized. line: "
                + token.getLine());
    }

    return node;
}

Come puoi vedere i metodi arg() e argLi() sono chiamati recursivelly, ed è così che l'ho implementato per evitare loop infiniti in modo efficiente.

Sono abbastanza sicuro che questa tecnica ti possa aiutare con il tuo problema.