Analisador Sintático com Representação

• Gramática ALisP
  • Geradores de λ
  • Primeiros e Seguintes
  • Diretores
• Representação de Árvores
• Analisador Sintático com Representação

Embora a função principal da análise sintática seja determinar se p ∈ L(G), aqui pretende-se ir além dessa resposta e obter a representação de p em termos da sua árvore (simplificada) de derivação na gramática G.

Gramática ALisP

Em termos de sintaxe a linguagem é a linguagem dos parêntesis equilibrados, com átomos, definida pela seguinte gramática, que designamos ALisP:

Expr -> atom | ( Seq )
Seq -> λ | Expr Seq 

onde atom representa um terminal átomo isto é, uma "palavra contígua": uma string não vazia sem espaços nem parêntesis.

Os átomos podem (devem!) ser representados pela sua própria sub-gramática. Para o efeito pretendido (análise sintática com representação) esse exercício iria apenas acrescentar ruído. Em vez disso, é implementado o teste is_atom(x), posteriormente usado pelo analisador sintático.

Para implementar o analisador sintático LL(1) é preciso calcular os diretores de cada produção.

Geradores de λ

Primeiros e Seguintes

Diretores

A tabela dos Diretores indica que a gramática ALisP é LL(1), pelo que pode ser aplicado o método dado no respetivo capítulo para construir um analisador sintático. Porém, também se pretende obter a representação da (árvore simplificada da derivação da) palavra.

Representação de Árvores

Como já foi tratado acima, qualquer árvore pode ser representada em Python por tuple aninhados. Mais especificamente:

Representação de nós em Python. O nó com com conteúdo x e descendentes d1, ..., dn, em que x e os di são valores Python, é representado pelo tuple

(x, d1, ..., dn)

Por convenção a representação das folhas não usa parêntesis. Em vez de (x) usa-se apenas x.

Por exemplo, a árvore de 2 + (3 * 4) é representada por

('+', 2, ('*', 3, 4))

Analisador Sintático com Representação

O analisador sintático com representação é implementado a partir da base definida no capítulo sobre a análise sintática LL(1). Acrescenta-se uma forma de se obter a representação em árvore e de tratar da especificidade dos átomos.

Para a implementação do analisador sintático compensa considerar com algum detalhe o contexto em que a análise LL(1) decorre. Em particular, importa tratar rigorosamente o processamento do avanço, de consumir e dos erros.

Contexto LL(1) Especificamente, uma instância c da classe ContextLL1:

• É construída com a palavra a ser analisada.
• c.next() devolve o próximo símbolo da palavra, se existir; caso contrário devolve None.
• c.consume(x) consome o próximo símbolo se o valor deste for x; caso contrário levanta uma exceção.
• c.error(m) levanta uma exceção com a mensagem m.
• Adicionalmente, c.is_complete() testa se não existe seguinte.

class ContextLL1:
    """Tracks and supports the state of a LL1 parsing process."""
    def __init__(self, word):
        self.word = word
        self.pos = 0

    def is_complete(self):
        """Checks if the parsing process is complete."""
        return self.pos >= len(self.word)

    def next(self):
        """Returns the next (unread) token."""
        if not self.is_complete():
            return self.word[self.pos]
        else:
            return None

    def consume(self, symbol):
        """'Consumes' symbol, advancing if possible."""
        if not self.is_complete() and self.next() == symbol:
            self.pos += 1
        else:
            self.error(f"** ERROR ** Can't CONSUME '{symbol}' while expecting '{self.next()}'.")

    def error(self, message):
        """Error handling."""
        raise Exception(f"{message}\nWord: {self.word}\nRead: {self.word[self.pos:]}\nUnread: {self.word[:self.pos]}")

    def __repr__(self):
        """String representation."""
        return f"\"{' '.join(self.word[:self.pos])}\" | \"{' '.join(self.word[self.pos:])}\""

Suporte. São necessárias algumas funções de suporte. Em particular

• tokenize(text) aceita uma string e devolve a lista das sub-palavras separadas por espaços, com tratamento especial dos parêntesis.
• is_atom(symbol) testa se symbol é um átomo: uma string não vazia e sem ocorrências de espaços ou parêntesis.
• atom_value(atom) devolve o "valor" do átomo atom, conforme atom pode ser convertido num ìnt senão num float senão no próprio atom.

def tokenize(text):
    """
    Converts a string to a list of tokens.
    """
    text = ''.join(ch for ch in text if ch.isprintable())
    text = text.replace("(", " ( ").replace(")", " ) ")
    tokens = text.split(" ")
    tokens = [tok.strip() for tok in tokens]
    tokens = [tok for tok in tokens if len(tok) > 0]
    return tokens

def is_atom(symbol):
    """
    Tests if a symbol is an atom.
    """
    return isinstance(symbol, str) and \
        len(symbol) > 0 and \
        (not ' ' in symbol) and \
        (not '(' in symbol) and \
        (not ')' in symbol)

def atom_value(atom):
    """
    Gets the value of an atom. BAD BAD NOT GOOD CODE.
    """
    value = None
    try:
        value = float(atom)
        (d, i) = math.modf(value)
        value = int(i) if d == 0 else value
    except:
        value = atom
    return value

• A implementação do analisador sintático, segundo o processo LL(1), consiste em definir uma função para cada variável da gramática ALisP e, em cada uma dessas funções, usar o avanço e os diretores para "percorrer" a regra adequada.
• A implementação LL(1) base é aumentada de forma se obter uma representação parcial em cada função associada.
• Todo o processo da análise sintática com representação é concretizado em parse(text). Esta função aceita como argumento text, uma string, e, se corresponder a uma palavra gerada pela gramática, devolve a respetiva representação em árvore.

#
# Rule            | Dir
# ----------------|-------
# Expr -> ( Seq ) | (
# Expr -> atom    | atom
#
def proc_Expr(context):
    next_symbol = context.next()
    if next_symbol == "(":
        context.consume("(")
        seq = proc_Seq(context)
        context.consume(")")
        return seq
    elif is_atom(next_symbol):
        context.consume(next_symbol)
        return atom_value(next_symbol)
    else:
        context.error(f"** ERROR ** Can't use Expr with next '{next_symbol}'.")
#
# Rule            | Dir
# ----------------|-------
# Seq -> Expr Seq | atom (
# Seq -> nil      | )
#
def proc_Seq(context):
    next_symbol = context.next()
    if is_atom(next_symbol) or next_symbol == "(":
        e = proc_Expr(context)
        s = proc_Seq(context)
        return (e,) + s
    elif next_symbol == ")":
        return tuple()
    else:
        context.error(f"** ERROR ** Can't use Seq with next '{next_symbol}'.")

def parse(text):
    word = tokenize(text)
    if all(is_atom(x) or x in "()" for x in word):
        context = ContextLL1(word)
        expr = proc_Expr(context)
        return expr
    else:
        return None

A implementação do processo de análise sintática chega ao fim da aplicação dos capítulos anteriores.

Recapitulando o que foi feito até aqui:

• Definiu-se uma gramática para especificar a sintaxe da ALisP.
• Essa gramática é LL(1) e implementou-se um analisador sintático que devolve uma representação em árvore da palavra dada.

Se tivesse sido escolhida uma linguagem com sintaxe mais complexa poderia ser necessário um analisador LR(1). Porém, o objetivo aqui é ir além da matéria anterior, implementando um interpretador da ALisP.