Sete Classes,
Quatro Roteiros

Uma calculadora mínima: só + e -, com números de vários dígitos. São válidas:

1
1+1
1+2+3
11-22-33

A gramática que descreve isso cabe numa linha:

EXPRESSION → NUMBER { ( "+" | "-" ) NUMBER }

E a pergunta da aula é: como transformar essa regra em algo fácil de implementar?

É uma terceira forma de representar a mesma gramática — e a mais próxima do código que virá depois. Em vez de símbolos, um trilho: você entra pela esquerda, percorre os caminhos possíveis e sai pela direita. Toda rota completa é uma cadeia válida.

O Lexer recebe caracteres e devolve tokens — os "átomos" do código-fonte. Ele agrupa 1 e 2 num único INT(12), descarta espaços, e não tem opinião nenhuma sobre ordem.

O Parser não vê caracteres. Ele recebe a sequência de tokens e faz uma única pergunta: essa ordem obedece à gramática?

Acompanhe o Parser percorrendo o diagrama. Troque o exemplo para ver a cadeia que sobra tokens:

O run() recebe o código, cria o Lexer, posiciona no primeiro token, chama parse_expression() e — este é o ponto — confere se o próximo token é EOF.

def run(code):
    Parser.lexer = Lexer(code)
    Parser.lexer.select_next()           # posiciona no primeiro token
    result = Parser.parse_expression()

    if Parser.lexer.next.type != "EOF":   # ← sem isto, "1+2 3" passaria
        raise Exception(...)

    return result

A partir daqui a disciplina deixa de ser sobre gramáticas no papel. A Aula 6 pega esse mesmo parser e o faz respeitar precedência; a Aula 8 o faz construir uma árvore em vez de calcular.

A aula parte de um problema concreto: descrever o formato de um endereço de e-mail. É o caso perfeito porque um e-mail tem estrutura, mas não tem aninhamento — e é exatamente essa a fronteira das linguagens regulares.

Uma linguagem regular pode ser descrita de três jeitos, e os três têm exatamente o mesmo poder. Para L = { abn : n ≥ 0 }:

S → a B
B → b B  |  ε

Os três operadores das expressões regulares:

A intuição em uma frase: se uma linguagem regular tem palavras arbitrariamente longas, o autômato que a reconhece precisa repetir algum estado — ele tem um número finito de estados e a palavra não tem limite. Todo estado repetido é um ciclo, e ciclo pode ser percorrido quantas vezes você quiser.

L regular  ⇒  ∃ p  tal que toda w ∈ L com |w| ≥ p se escreve  w = x y z  com:

    |xy| ≤ p        (o ciclo acontece cedo)
    |y| > 0          (o ciclo consome pelo menos um símbolo)
    x yi z ∈ L       para todo i ≥ 0

O uso é sempre por contradição. Para L = { anbn }: suponha regular, pegue o p garantido, escolha w = apbp. Como |xy| ≤ p, o trecho y só contém a. Bombeando com i = 2 você ganha a sem ganhar b — a igualdade quebra. Contradição.

Dizer que uma classe é fechada sob uma operação significa: se você começa com linguagens da classe e aplica a operação, o resultado continua na classe. As regulares são generosas nesse quesito — fecham sob praticamente tudo.

Isso não é curiosidade: é ferramenta de prova. Se L ∩ R não for regular e R for regular, então L não podia ser regular — senão a interseção seria. O detalhamento completo, comparando com as livres de contexto, está na Parte II, aba Fechamento.

Para linguagens regulares, várias perguntas têm resposta algorítmica garantida — o que, como a Aula 9 vai mostrar, deixa de valer nas classes mais acima:

EXPRESSION = TERM,   { ("+" | "-"), TERM }   ;
TERM       = FACTOR, { ("*" | "/"), FACTOR } ;
FACTOR     = ("+" | "-"), FACTOR | "(", EXPRESSION, ")" | NUMBER ;

A primeira regra lê-se assim: uma expressão começa com um TERM e pode ser seguida por zero ou mais blocos do tipo + TERM ou - TERM. A segunda faz o mesmo para multiplicação e divisão.

Porque parse_expression() chama parse_term(), que chama parse_factor(). O TERM termina de resolver 4*2 antes de devolver esse resultado para o EXPRESSION. Acompanhe o vaivém:

E                      # parse_expression começa
↓
  T                    # chama parse_term
  ↓
    F  lê 3            # parse_factor consome o 3
  ↑
  T  vê + e termina    # + não é dele, devolve 3
↑
E  consome o +
↓
  novo T
  ↓
    F  lê 4
  ↑
  T  vê *              # * É dele, fica com ele
  ↓
    novo F  lê 2
  ↑
  T  termina 4 * 2 = 8 # resolve antes de devolver
↑
E  termina 3 + 8 = 11

Repare na linha "T vê + e termina": o + não pertence àquele nível, então o TERM devolve o que tem e deixa o + para quem o chamou. Esse deixar para o de cima é o mecanismo inteiro da precedência.

O depurador da aba v1.1, na Parte III, mostra esses quadros de chamada empilhando e desempilhando de verdade, cada um com o seu próprio result.

Cada regra da gramática é um trilho. Você entra pela esquerda, segue os caminhos e sai pela direita — e um retângulo com nome de regra significa "vá percorrer aquele outro trilho e volte". Digite uma expressão e veja o percurso acontecer.

Em -3, o - não é subtração entre dois operandos: ele se aplica diretamente ao 3. Por isso a gramática permite FACTOR → "-" FACTOR e FACTOR → "+" FACTOR.

E como FACTOR chama outro FACTOR, construções como --3, +-3 e +--++3 funcionam sem nenhum código específico para unários encadeados. É recursão fazendo o trabalho.

FACTOR → "(" EXPRESSION ")". Quando o parser encontra (, ele começa uma EXPRESSION nova lá dentro. O nível mais interno volta ao mais externo, e o ciclo se fecha:

(2 + 3) * 4

FACTOR
↓
  (
  ↓
    EXPRESSION        # de volta ao topo da gramática
    ↓
      2 + 3
  ↓
  )
↑
esse FACTOR inteiro vira o operando esquerdo do *

Quase nada — quatro tokens novos: MULT, DIV, OPEN_PAR, CLOSE_PAR, somados aos já existentes PLUS, MINUS, INT e EOF. Para a análise léxica, * e + são igualmente triviais: ela não sabe nem se importa que um amarra mais forte que o outro.

A partir do Roteiro 5 a linguagem deixa de ser uma expressão solta e vira um programa: várias linhas, variáveis e saída. Vale ver agora, porque quase tudo que você já entendeu continua igual — e o que muda, muda pouco.

A definição formal continua a mesma quádrupla:

G = ( V , Σ , P , A )

    V   vocabulário           P   produções
    Σ   terminais             A   símbolo inicial

A novidade está na forma das regras:

α → β        com  α ∈ N  (um único NÃO TERMINAL)
                    β ∈ V*  (qualquer combinação de terminais e não terminais)

Em português: o lado esquerdo é sempre um não terminal sozinho — daí "livre de contexto": não importa o que está em volta, a regra pode ser aplicada. O lado direito, porém, é livre.

A gramática do aninhamento:

A → ( A )
A → a

gera:  a  ·  (a)  ·  ((a))  ·  (((a)))  …

Ela não é regular, porque A → (A) tem um terminal de cada lado do não terminal. Uma gramática linear só admite o não terminal numa ponta.

A aula tenta montar um autômato finito para essa linguagem. O resultado aceita os casos certos — e também aceita lixo:

O diagnóstico: o autômato não tem memória para casar aberturas com fechamentos numa quantidade arbitrária. Ele sabe que leu um parêntese; não sabe quantos.

estado + símbolo atual

estado + símbolo atual + pilha

A regra para parênteses é de uma simplicidade desconcertante: lê ( → empilha; lê ) → desempilha. A pilha guarda exatamente quantas aberturas estão pendentes.

Rode o autômato. Se ao final a entrada acabou e a pilha está vazia, a palavra é aceita:

O PDA que a aula constrói usa um critério de aceitação diferente do habitual: não há estado final. A palavra é aceita quando a entrada terminou e a pilha está vazia. Isso parece um detalhe técnico, mas é o que torna a equivalência do próximo passo elegante de provar.

O teorema vale nos dois sentidos:

É o mesmo tipo de correspondência que você já tinha visto um nível abaixo:

Toda estrutura aninhada é livre de contexto e não regular. Por isso nenhuma das três abaixo pode ser validada corretamente só com expressão regular:

Uma derivação é o passo a passo de como a gramática gera uma cadeia. Você começa no símbolo inicial e vai trocando não-terminais pelas suas regras, até sobrar só texto. Para ver a ideia limpa, a aula usa a menor gramática interessante que existe:

S → a S b  |  ε        # ε (épsilon) = a palavra vazia

Ela gera ab, aabb, aaabbb… sempre a mesma quantidade de a e de b — o mesmo padrão dos parênteses da Aula 7, e pelo mesmo motivo não é regular.

Avance os passos e veja a derivação e a árvore crescerem juntas. A árvore é só a derivação desenhada: cada substituição vira um nó com seus filhos.

Uma gramática é ambígua quando uma mesma cadeia admite duas árvores de derivação diferentes. Parece detalhe teórico. Não é: significa que o mesmo programa pode ter dois significados. Considere a gramática ingênua que qualquer um escreveria primeiro:

E → E "+" E  |  E "*" E  |  number

Ela aceita 3+4*2. O problema é como — de duas formas, ambas válidas segundo as regras:

É aqui que EXPRESSION, TERM e FACTOR deixam de parecer burocracia. Eles não foram inventados para organizar o código — foram inventados para eliminar a ambiguidade. Um TERM nunca pode conter um + solto; para isso teria que descer até FACTOR e entrar num parêntese. Então a Árvore 2 acima simplesmente não é derivável. Sobra uma, e só uma.

Ambiguidade não é problema só de contas. O exemplo mais famoso em linguagens de programação é o else pendurado:

if (a == b)
    if (c <= n)
        d++;
else
    d--;

Esse else pertence a qual if? A indentação sugere o primeiro, mas indentação não é gramática:

if (a == b) {
    if (c <= n)
        d++;
    else
        d--;
}

if (a == b) {
    if (c <= n)
        d++;
}
else
    d--;

Com a == b verdadeiro e c <= n falso, a Leitura A executa d-- e a Leitura B não executa nada. Comportamentos diferentes, mesmo texto.

Resolvida a ambiguidade, sobra uma árvore — mas ela é grande demais. Para chegar ao número 3 em 3+4*2, a árvore de derivação desce por EXPRESSION → TERM → FACTOR → NUMBER, mesmo não havendo multiplicação nenhuma naquele ramo.

Esses nós cumpriram o papel deles — provar que a cadeia obedece à gramática — e depois disso não servem para mais nada. A AST é o que sobra quando você joga fora o andaime. Por isso ela é abstrata: o operador, que na derivação era um terminal consumido de passagem, vira o nó; e os não-terminais, que eram nós, desaparecem.

Na Parte II, aba Árvores, há um gerador que desenha as duas lado a lado para a expressão que você digitar.

A avaliação é recursiva: cada nó resolve a própria operação, mas só depois de pedir aos filhos que resolvam a parte deles. Acompanhe a conversa para 3+4*2:

Três coisas para guardar dessa conversa. A execução vai de baixo para cima — a raiz é a última a produzir um valor, e é o valor final. Nenhum nó sabe quem é o seu pai. E o + não faz ideia de que o filho direito é uma multiplicação: ele pede um número e recebe um número. É exatamente isso que o depurador da aba v1.2 anima nó a nó.

Um parser LL parte do símbolo inicial e vai expandindo regras até chegar na cadeia. As três letras significam:

O exemplo do material:

A → a A b  |  c              L = { am c bm : m ≥ 0 }

Essa gramática é LL(1): olhando um único token, a decisão já está tomada. Se o próximo for a, use A → aAb. Se for c, use A → c. Nunca há dúvida.

def parse_factor():
    token = Parser.lexer.next        # k = 1: um token, e só

    if token.type == "INT":        # escolhe a produção
        ...
    if token.type in ("PLUS", "MINUS"):
        ...
    if token.type == "OPEN_PAR":
        ...

Um parser LR faz o caminho inverso: parte da cadeia e vai reduzindo pedaços até sobrar o símbolo inicial. Ele trabalha com uma pilha e duas operações:

Acompanhe um shift-reduce completo. A gramática é E → E+T | T e T → n, e a entrada é n+n:

Repare no formato: a pilha cresce com os shifts e encolhe com os reduces, e no fim resta exatamente E. Foi o caminho oposto ao da árvore de derivação da Aula 8, que ia de S para a cadeia.

Nem toda gramática livre de contexto é tratável do mesmo jeito. Elas se encaixam umas nas outras:

A segunda metade da aula troca "como analisar" por "o que é possível analisar". Os três tópicos estão desenvolvidos em detalhe na Parte II, cada um na sua aba:

A gramática da linguagem

Uma gramática define quais sequências de símbolos são válidas. A do seu compilador tem três regras, e cada uma vira uma função — quase palavra por palavra.

EXPRESSION = TERM, { ("+" | "-"), TERM } ;
TERM       = FACTOR, { ("*" | "/"), FACTOR } ;
FACTOR     = NUMBER | ("+" | "-"), FACTOR | "(", EXPRESSION, ")" ;
NUMBER     = DIGIT, { DIGIT } ;
DIGIT      = "0" | "1" | ... | "9" ;

O dicionário EBNF → código

Derivação: gerando uma string a partir da gramática

Uma string pertence à linguagem se existir um caminho do símbolo inicial até ela. Cada passo substitui um não-terminal pela sua regra. Compare as duas expressões — repare onde o 3*4 aparece agrupado:

BNF, EBNF, e o que a recursão à esquerda revela

A mesma linguagem, escrita em BNF pura — sem as chaves de repetição:

<expression> ::= <term>
               | <expression> "+" <term>
               | <expression> "-" <term>

Onde a EBNF usa { }, a BNF precisa de recursão. E repare onde: <expression> aparece à esquerda do operador. Isso se chama recursão à esquerda, e não é detalhe de escrita — ela codifica a associatividade:

O while que acumula da esquerda para a direita no parse_expression() é a tradução direta dessa recursão à esquerda. Por isso 10-3-2 dá 5 no seu código sem você ter pensado no assunto.

O Lexer é um autômato finito

Um autômato finito determinístico (AFD) é a máquina mais simples que existe para reconhecer padrões: um conjunto de estados, uma transição por símbolo lido, e alguns estados marcados como de aceitação. Ele tem uma limitação definidora — nenhuma memória além do estado atual. Não conta, não empilha, não lembra o que veio antes.

E é exatamente isso que o seu select_next() é. A variável position não é memória do autômato: é só o ponteiro de leitura da fita.

Rode o autômato

Digite algo e avance caractere a caractere. Observe que o estado nunca guarda mais do que "estou lendo um número" ou "não estou".

O lema do bombeamento

O lema do bombeamento (pumping lemma) é uma ferramenta para provar que uma linguagem NÃO é regular — ou seja, que nenhum autômato finito consegue reconhecê-la, por mais estados que você lhe dê.

Ele importa muito concretamente aqui: é a razão formal de o FACTOR precisar chamar a si mesmo.

A intuição é simples: um autômato com p estados que lê uma palavra de p ou mais símbolos precisa repetir algum estado — não há estados suficientes para todos serem distintos. O trecho lido entre as duas visitas ao mesmo estado forma um laço. E um laço pode ser percorrido quantas vezes você quiser: zero, uma, mil. Se a linguagem é regular, todas essas repetições continuam válidas.

Então, para provar que algo não é regular, basta achar uma palavra que quebra ao ser bombeada.

Aplicando: parênteses balanceados não são regulares

Considere L = { (ⁿ )ⁿ : n ≥ 1 } — a linguagem dos parênteses que abrem e fecham na mesma quantidade. Suponha, por absurdo, que seja regular. Então existe p, e tomamos w = (^p)^p.

Pela condição (1), xy cabe nos primeiros p símbolos — que são todos abre-parênteses. Logo y só contém (. Bombeando com i = 2, a palavra ganha parênteses abertos a mais e nenhum fechado. O balanço quebra. Contradição — a linguagem não é regular.

Mexa nos controles e veja a contradição acontecer:

Até o Roteiro 2 a linguagem inteira era regular — sem parênteses, nada se aninhava, e em tese um único autômato finito daria conta. O Roteiro 3 é o momento em que ela sobe de classe.

A versão para linguagens livres de contexto

O mesmo raciocínio sobe um andar. Se uma CFL tem palavras arbitrariamente longas, a árvore de derivação de uma palavra suficientemente comprida precisa ser alta — e numa árvore alta, algum não-terminal reaparece no mesmo caminho, porque a gramática tem um número finito deles.

L livre de contexto  ⇒  ∃ n  tal que toda z ∈ L com |z| ≥ n se escreve  z = u v w x y  com:

    v x ≠ ε          (pelo menos um dos dois trechos é não vazio)
    |v w x| ≤ n       (os dois trechos ficam perto um do outro)
    u vi w xi y ∈ L    para todo i ≥ 0

O exemplo clássico: anbncn não é livre de contexto

A pilha de um PDA consegue casar duas quantidades — abre e fecha, a e b. Casar três ao mesmo tempo é demais para ela, e o pumping lemma prova isso.

Suponha CFL, pegue o n garantido e escolha z = anbncn. Como |vwx| ≤ n, o trecho vwx é curto demais para tocar as três letras — ele cobre no máximo duas delas (a e b, ou b e c). Bombeando com i = 2, as letras tocadas crescem e a terceira fica para trás. As três quantidades deixam de ser iguais. Contradição.

Propriedades de fechamento

Dizer que uma classe de linguagens é fechada sob uma operação significa uma coisa só: se você pega linguagens daquela classe e aplica a operação, o resultado continua na classe.

L₁ , L₂ regulares   ⇒   L₁ ∪ L₂  é regular     ✓ fechada sob união
L₁ , L₂ livres de contexto   ⇒   L₁ ∩ L₂  pode NÃO ser livre de contexto

Isso parece contabilidade abstrata, mas é ferramenta de prova — e é assim que cai em avaliação.

A tabela que você precisa saber

Como usar isso numa prova

# Para provar que L NÃO é regular usando fechamento:

1. suponha que L é regular
2. escolha uma linguagem R comprovadamente regular
3. como regulares fecham sob ∩, então L ∩ R seria regular
4. mostre (por pumping) que L ∩ R NÃO é regular
5. contradição ⇒ L não era regular

A vantagem sobre aplicar pumping direto em L: às vezes L é bagunçada demais para escolher uma palavra boa, mas L ∩ R fica limpinha.

A hierarquia de Chomsky

Quatro classes encaixadas, cada uma estritamente maior que a anterior. A posição de uma linguagem na hierarquia responde a uma pergunta prática: que tipo de máquina é preciso construir para reconhecê-la?

Onde o seu compilador está

Essa última linha é a moral da história. "Toda variável usada foi declarada" é uma restrição de tipo 1 disfarçada — gramática livre de contexto nenhuma expressa isso. Por isso todo compilador tem uma fase semântica separada: não é preguiça de projeto, é uma fronteira formal.

Duas árvores diferentes

A palavra "árvore" é usada para duas coisas distintas, e confundi-las atrapalha. A árvore de derivação registra cada regra da gramática que foi aplicada. A AST guarda só o que é necessário para calcular. Compare as duas para a mesma expressão:

A árvore de derivação é alta e repetitiva: para chegar ao número 2, é preciso descer por EXPRESSION → TERM → FACTOR → NUMBER, mesmo que nenhuma multiplicação exista ali. Esses nós intermediários provam que a string obedece à gramática — e depois disso não servem para mais nada.

O evaluate() é um percurso em pós-ordem

Percorrer uma árvore tem nomes conforme a ordem em que se visita a raiz:

Faz sentido que seja pós-ordem: um BinOp não tem como somar antes de saber quanto valem os dois filhos. A raiz é sempre a última a produzir um valor — e é o valor final.

def evaluate(self):
    left  = self.children[0].evaluate()   # 1. desce à esquerda
    right = self.children[1].evaluate()   # 2. desce à direita
    ...                                   # 3. só então opera — pós-ordem

No depurador da aba v1.2, mais abaixo, você vê esse percurso acontecendo: os nós acendem descendo até as folhas e os valores vão aparecendo de baixo para cima.

O enunciado pedia apenas um main.py que recebesse '1+ 2 -3' e imprimisse 0 — nenhuma classe era exigida. Mesmo assim o código já nasceu dividido em três, porque o problema tem uma tensão que só a divisão resolve.

Depurador — gramática do Roteiro 1

Só + e -. Não há precedência nem parênteses: o resultado é acumulado da esquerda para a direita numa única variável.

Nenhuma classe nova, nenhuma funcionalidade nova. A gramática é idêntica à do Roteiro 1 — mesmos tokens, mesmos resultados, mesma bateria de testes. O que muda é só quem executa o quê, e por quê.

class Parser:
    def __init__(self):
        self.tokenizer = None

    def parse_expression(self):
        ...

# uso:
print(Parser().run(sys.argv[1]))

class Parser:
    lexer = None

    @staticmethod
    def parse_expression():
        ...

# uso:
print(Parser.run(sys.argv[1]))

Estático significa que o membro pertence à classe, não a um objeto. Faz sentido aqui porque não existe cenário em que dois Parser analisem coisas diferentes ao mesmo tempo: há um programa sendo compilado, e um só.

Depurador — gramática do Roteiro 2

A mesma gramática do Roteiro 1. O que mudou é interno: o token vem do Lexer sob demanda, e as chamadas são estáticas.

# 1. Lexer: mais um símbolo de um caractere
elif char == "^":
    self.position += 1
    self.next = Token("XOR", "^")

# 2. Parser: o XOR entra na MESMA condição do while
while Parser.lexer.next.type in ("PLUS", "MINUS", "XOR"):
    ...
    if operator == "PLUS":
        result += Parser.lexer.next.value
    elif operator == "MINUS":
        result -= Parser.lexer.next.value
    else:
        result ^= Parser.lexer.next.value

A linguagem cresce de verdade pela primeira vez, e a resposta não é uma classe nova — são dois métodos.

SYMBOLS = {
    "+": "PLUS",  "-": "MINUS",
    "*": "MULT",  "/": "DIV",
    "(": "OPEN_PAR",  ")": "CLOSE_PAR",
}

Depurador — gramática do Roteiro 3

Agora com os três níveis. Acompanhe a pilha de chamadas: ela cresce ao entrar em parse_term e parse_factor, e cada quadro tem o seu próprio resultado parcial.

FACTOR = NUMBER
       | ("+"|"-"), FACTOR
       | "(", EXPRESSION, ")" ;

FACTOR = ("+"|"-"), FACTOR
       | BASE, { "**", BASE } ;

BASE   = NUMBER
       | "(", EXPRESSION, ")" ;

# 1. Lexer: o ** precisa ser testado ANTES do *, senão vira dois MULT
if self.source.startswith("**", self.position):
    self.position += 2
    self.next = Token("POWER", "**")
elif char in Lexer.SYMBOLS:
    ...

# 2. Parser: FACTOR trata o unário e delega; o laço de ** opera sobre BASE
def parse_factor():
    if Parser.lexer.next.type == "PLUS":
        Parser.lexer.select_next()
        return Parser.parse_factor()
    if Parser.lexer.next.type == "MINUS":
        Parser.lexer.select_next()
        return -Parser.parse_factor()

    result = Parser.parse_base()
    while Parser.lexer.next.type == "POWER":
        Parser.lexer.select_next()
        result **= Parser.parse_base()
    return result

def parse_base():          # o pedaço que sobrou: só número e parêntese
    ...

A mudança mais profunda dos quatro roteiros, e a que menos altera os resultados: a bateria de testes é exatamente a mesma do Roteiro 3. O que muda é quando a conta acontece.

while ... in ("PLUS", "MINUS"):
    ...
    if operator == "PLUS":
        result += Parser.parse_term()
    else:
        result -= Parser.parse_term()

# devolve um NÚMERO

while ... in ("PLUS", "MINUS"):
    operator = Parser.lexer.next.value
    Parser.lexer.select_next()
    result = BinOp(operator,
                   [result, Parser.parse_term()])

# devolve um NÓ

O programa passa a ter dois tempos: montar (texto → árvore) e avaliar (árvore → número). O main() junta os dois em uma linha: print(Parser.run(code).evaluate()).

class Node(ABC):
    def __init__(self, value, children):
        self.value = value
        self.children = children

    @abstractmethod
    def evaluate(self):
        pass

Depurador — gramática do Roteiro 4

Mesma gramática do Roteiro 3, mas agora você vê a árvore sendo montada nó a nó e, depois, o evaluate() descendo até as folhas e subindo com os valores.

FACTOR = ("+"|"-"), FACTOR | BASE, { "!" } ;
BASE   = NUMBER | "(", EXPRESSION, ")" ;

UnOp('-')
   UnOp('!')
      IntVal(3)

# 1. Lexer: uma entrada a mais na tabela
SYMBOLS = { ..., "!": "FACT" }

# 2. UnOp: mais um ramo no evaluate, com a checagem de negativo
if self.value == "!":
    if operand < 0:
        raise Exception(f"[Semantic] Factorial of negative number {operand}")
    return math.factorial(operand)

# 3. Parser: o mesmo split do extra anterior, com o laco pos-fixo
def parse_factor():
    if Parser.lexer.next.type in ("PLUS", "MINUS"):
        operator = Parser.lexer.next.value
        Parser.lexer.select_next()
        return UnOp(operator, [Parser.parse_factor()])

    result = Parser.parse_base()
    while Parser.lexer.next.type == "FACT":
        Parser.lexer.select_next()
        result = UnOp("!", [result])    # embrulha o que ja existia
    return result

O Roteiro 5 é o maior salto do curso: o compilador deixa de avaliar uma expressão e passa a executar um programa, uma instrução por linha, com variáveis que guardam valores entre uma linha e outra. A meta do roteiro:

// Comentário!
x1 = 3
y2 = 4
z_final = x1 + y2
Println(z_final)

Esta aba é em Java, com o seu código de verdade: o painel "Código" mostra o main.java da tag v2.0.2, sem nenhuma alteração. O depurador reimplementa cada método e foi conferido contra o javac: mesmas saídas e mesmas mensagens de erro.

A gramática

PROGRAM    = { STATEMENT } ;
STATEMENT  = ( λ | IDENTIFIER, "=", EXPRESSION | "Println", "(", EXPRESSION, ")" ), "\n" ;
EXPRESSION = TERM, { ("+" | "-"), TERM } ;
TERM       = FACTOR, { ("*" | "/"), FACTOR } ;
FACTOR     = NUMBER | IDENTIFIER | ("+" | "-"), FACTOR | "(", EXPRESSION, ")" ;
IDENTIFIER = LETTER, { LETTER | DIGIT | "_" } ;
NUMBER     = DIGIT, { DIGIT } ;

Node raiz = Parser.run(codigoFonte);
int resultado = raiz.evaluate();
System.out.println(resultado);

String codigoLimpo = PrePro.filter(conteudo);
Node raiz = Parser.run(codigoLimpo);
SymbolTable st = new SymbolTable();
raiz.evaluate(st);  // sem println aqui

Depurador animado — Roteiro 5

Veja o \n virar o token END na fita, o parseStatement() escolher o caminho pelo primeiro token e o Block raiz ganhar um filho por linha (inclusive os NoOp das linhas vazias). Na fase 2, a SymbolTable nasce vazia e vai sendo preenchida: a linha pisca em laranja quando é escrita e fica azul quando é lida.

Base de testes

O roteiro pede um programa com bloco de instruções, atribuições com operações entre variáveis e impressão, além dos testes de variável inválida e de variável inexistente.

Perguntas do Roteiro 5 · treino e extra credit

Três tipos de pergunta: sobre o roteiro (conceitos), sobre as funções (o porquê de cada linha do seu código) e implemente você, no formato de extra credit e de prova: um símbolo novo, uma variável imutável… o que muda no Lexer, no Parser, na AST e na EBNF. Tente responder antes de abrir a resposta e marque ✓ sei ou ↺ revisar. As marcações ficam salvas neste navegador.

Até o Roteiro 5, todo programa rodava cada linha exatamente uma vez, de cima para baixo. O Roteiro 6 traz duas coisas novas: a execução passa a escolher um caminho (if/else) e a voltar para trás (for, que em Go faz o papel do while). Para isso aparecem os operadores booleanos e relacionais, as chaves de bloco e a leitura do terminal. A meta do roteiro é o fatorial:

i = 1
n = 5
f = 1
if n < 2 {
    f = 1
} else {
    for i < n || i == n {
        f = f * i
        i = i + 1
    }
}

Esta aba é em Java. O código ativo do depurador é uma referência do Roteiro 6, escrita no mesmo estilo de um main.java do Roteiro 5 (classes Lexer, Parser, Node, enum TipoToken). O enunciado pede que você escreva a sua própria EBNF: use isto para estudar, não para copiar.

A gramática (uma proposta)

O diagrama da aula é o de C, com parênteses no if. Adaptado para o Go, fica assim. As linhas marcadas com ★ são novas em relação ao Roteiro 5:

PROGRAM         = { STATEMENT } ;
BLOCK           = "{", { STATEMENT }, "}" ;                              ★
STATEMENT       = ( λ | ASSIGNMENT | PRINT | IF | FOR ), "\n" ;
ASSIGNMENT      = IDENTIFIER, "=", BOOL_EXPRESSION ;
PRINT           = "Println", "(", BOOL_EXPRESSION, ")" ;
IF              = "if", BOOL_EXPRESSION, BLOCK, [ "else", BLOCK ] ;          ★
FOR             = "for", BOOL_EXPRESSION, BLOCK ;                           ★
BOOL_EXPRESSION = BOOL_TERM, { "||", BOOL_TERM } ;                        ★
BOOL_TERM       = REL_EXPRESSION, { "&&", REL_EXPRESSION } ;              ★
REL_EXPRESSION  = EXPRESSION, { ("==" | ">" | "<"), EXPRESSION } ;         ★
EXPRESSION      = TERM, { ("+" | "-"), TERM } ;
TERM            = FACTOR, { ("*" | "/"), FACTOR } ;
FACTOR          = NUMBER | IDENTIFIER | ("+" | "-" | "!"), FACTOR
                | "(", BOOL_EXPRESSION, ")" | "Scanln", "(", ")" ;      ★

A precedência sai da escada de funções, igual ao Roteiro 3: quanto mais fundo o degrau, mais forte o operador. Da mais forte para a mais fraca: ! + - (unários) → * / → + - → == > < → && → ||. Por isso 1 + 2 * 3 == 7 && !0 || 0 se lê como (((1 + (2*3)) == 7) && (!0)) || 0. Carregue esse exemplo no depurador e veja a árvore.

} else if (c == '=') {
    next = new Token(ASSIGN, 0);
    position++;
}

} else if (c == '=') {
    if (source.charAt(position + 1) == '=') {
        next = new Token(EQ, 0);  position += 2;
    } else {
        next = new Token(ASSIGN, 0); position++;
    }
}

Depurador animado — Roteiro 6

Escreva um programa (ou escolha um exemplo) e aperte ▶ Rodar. Na fita, cada token entra quando o Parser chama selectNext(); os consumidos ficam riscados e o next fica em destaque. A pilha mostra quem chamou quem: a moldura vermelha está rodando, a verde está devolvendo um valor. Na AST, os nós surgem enquanto o Parser os cria e, na fase 2, acendem conforme o evaluate() desce e mostram o valor (↩) quando sobem. O código é o método Java que está rodando, com a linha acesa. A faixa colorida embaixo da linha do tempo mostra as fases: verde é o Léxico, azul o Sintático, laranja o Semântico.

Base de testes

O roteiro pede um programa com laços e condicionais usando and/or/not e leitura do terminal. Clique numa entrada para carregá-la no depurador. As saídas abaixo foram conferidas rodando a referência Java de verdade.

Pegadinhas

Perguntas do Roteiro 6 · treino e extra credit

Mesmo formato do Roteiro 5: sobre o roteiro, sobre as funções e implemente você (!= e >=, else if, for estilo C, break, repeat, tipagem forte…). Os exercícios adicionais do enunciado estão aqui.