Analisador de linguagem de programação (em Java) - Qual seria a melhor alternativa de design para um caso especial?

5

Antecedentes

Atualmente, estou projetando minha própria linguagem de programação como um projeto de pesquisa. Eu tenho a maior parte da gramática feita e escrita como gramática livre de contexto, e deveria estar funcionando como está. - Agora estou trabalhando no compilador real que deve traduzir o idioma em x86 binary assembly code , mais especificamente, estou trabalhando no parser (o front end).

A sintaxe da linguagem é, na maior parte, muito semelhante a Java / C / C ++. O analisador, que constrói uma representação intermediária a partir do código-fonte, funciona da seguinte maneira:

A gramática é construída como uma grande árvore na qual o código-fonte real determina apenas as folhas; Cada variável sintática (ou não terminal) tem sua própria classe, e cada uma dessas classes possui um método static get(byte[] source, int offset) que retorna uma nova folha (nó) ou null se a sintaxe do código fonte não se encaixa nessa estrutura não terminal. p>

Estou usando uma variação de predictive parsing , a propósito.

Para o não-terminal DataType , escolhi a seguinte estrutura gramatical:

DataType:
    PrimitiveDataType
 |  ArrayDataType
 |  ComplexDataType

ArrayDataType:
    DataType []

Eu mencionei que essa linguagem é orientada a objetos?

Portanto, o problema aqui é que quando o método DataType get é chamado, ele primeiro verifica se o seguinte é um tipo de dados primitivo, PrimitiveDataType 's get method é chamado. Supondo que temos uma matriz, isso retornaria null , portanto, ela continuará a verificar se é um ArrayDataType , chamando o método get .

Problema

Matrizes podem ser criadas a partir de qualquer tipo de dados, incluindo as próprias matrizes (que pareceriam com Type[][] ). Então, o que o método ArrayDataType 'co_de% faria é novamente chamar o método get DataType para descobrir de que tipo é a matriz. Infelizmente, é aí que a minha implementação do analisador falharia porque esse comportamento resulta em um loop!

Pergunta

Haveria alguma alternativa de design boa / melhor para isso?

    
por Kierrow 23.07.2012 / 17:56
fonte

4 respostas

2

Analisador preditivo selecionado (LL (k)) significa que você terá que resolver problemas de recursão à esquerda. Algoritmo para resolver recursões diretas e indiretas é claramente descrito na wikipedia:

link

Algumas informações podem ser encontradas em postagens aqui no StackOverflow:

link link link

Em linguagem humana (não científica :) "problema de recursão à esquerda" significa que você não pode infinitamente entrar em recursão com não-terminal (A - > Ab) repetidas vezes. Em algum momento você tem que alimentar o algoritmo do analisador com um terminal para violar um loop.

No BNF, isso pode parecer:

Problema de recursão:

NT: NT T
NT: T

Uma solução:

NT: T NT2
NT2: T NT2
NT2: 

Para sua gramática, isso pode parecer:

DataType:
    PrimitiveDataType ArrayDimensions
 |  ComplexDataType ArrayDimensions

ArrayDimensions:
    [] ArrayDimensions
 |

Se o seu gerador de analisadores não permitir produções vazias e / ou se você quiser processar os tipos de matriz separadamente, tente algo assim:

DataType:
    DataTypeName
 |  ArrayDataType

ArrayDataType:
    DataTypeName ArrayDimensions

DataTypeName:
    PrimitiveDataType
 |  ComplexDataType

ArrayDimensions:
    []
 |  [] ArrayDimensions
    
por 23.07.2012 / 20:52
fonte
2

O problema é que o uso de um analisador LL (1) pode levar à recursão à esquerda . Você pode evitar isso mudando para um analisador LR ou usando essa gramática para evitar a recursão:

DataType:
    PrimitiveDataType ArrayDataType
 |  ComplexDataType ArrayDataType

ArrayDataType:
    [] ArrayDataType
 |  (empty)

Se a análise não fizer parte do seu projeto, basta pesquisar por uma biblioteca / gerador de análise, provavelmente há muitos por aí.

    
por 23.07.2012 / 19:31
fonte
0

A chave aqui é simplesmente usar um analisador LR em vez de LL. Há uma razão pela qual praticamente nenhuma implementação realmente usa LL como é declarado, e é porque ela realmente não consegue reconhecer muitas gramáticas particularmente úteis.

    
por 23.07.2012 / 20:38
fonte
0

Esse problema que você está enfrentando parece com algo que já enfrentei. Nesse caso, deve ser implementado na classe Syntatic Analyzer , e sim, ele irá gerar uma árvore, seria de fato recursivo.

Por exemplo: no meu caso, eu tive que implementar uma maneira que a função recebesse uma lista de argumentos, então minha regra gramatical para lista de argumentos seria algo assim:

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

onde:

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

<ArgLi> é chamado recursivamente

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

Identifier = {ID Head}{ID Tail}*

Portanto, para implementar esse recurso, o comando tem delimitadores, portanto, mesmo que ele entre em um loop, ele verificará a regra e determinará a ação com base no token atual que estou procurando.

Por exemplo, digamos que eu queira escrever isto:

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

...

)

O código que minha linguagem segue para entender isso é:

/**
 * <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;
}

Como você pode ver, os métodos arg() e argLi() são chamados recursivamente, e é assim que eu o implementei para evitar infinitos loops de uma maneira eficiente.

Tenho certeza de que essa técnica pode ajudá-lo com seu problema.

    
por 23.07.2012 / 18:08
fonte