Analisador léxico, sintático e semântico

O objetivo principal é alguém que já tenha feito (possua) o projeto, mesmo que seja apenas o Analisador Léxico rodando.
Qualquer dessas linguagens (C, C++, C#, Java, Ruby ou Python), preferencia java e python.

Projeto:
Implementar um analisador léxico para a linguagem PasC cuja descrição encontra-se na seção 4.

O analisador léxico deverá ser implementado com o auxílio de um autômato finito determinístico. Ele deverá reconhecer um lexema e retornar, a cada chamada, um objeto da classe Token, representando o token reconhecido de acordo com o lexema encontrado.

Para facilitar a implementação, uma Tabela de Símbolos (TS) deverá ser usada. Essa tabela conterá, inicialmente, todas as palavras reservadas da linguagem. À Medida que novos tokens forem sendo reconhecidos, esses deverão ser consultados na TS antes de serem cadastrados e retornados.
Somente palavras reservadas e identificadores serão cadastrados na TS. Não é permitido o cadastro de um mesmo token mais de uma vez na TS.

Resumindo, seu Analisador Léxico deverá imprimir a lista de todos os tokens reconhecidos, assim como mostrar o que está cadastrado na Tabela de Símbolos. Na impressão dos tokens, deverá aparecer a tupla <nome, lexema> assim como linha e coluna do token.

Além de reconhecer os tokens da linguagem, seu analisador léxico deverá detectar possíveis erros e reportá-los ao usuário. O programa deverá informar o erro e o local onde ocorreu (linha e coluna), lembrando que em análise léxica tem- se 3 tipos de erros: caracteres desconhecidos (não esperados ou inválidos), string não-fechada antes de quebra de linha e comentário não-fechado antes do fim de arquivo.

Espaços em branco, tabulações, quebras de linhas e comentários não são tokens, ou seja, devem ser descartados/ignorados pelo referido analisador.

Na gramática do PasC, os terminais de um lexema, bem como as palavras reservadas, estão entre aspas duplas para destacá-los, ou seja, as aspas não são tokens.

1.2 O que entregar?
Você deverá entregar nesta etapa:

Uma figura apresentando o Autômato Finito Determinístico para reconhecimento dos tokens (dê uma olhada na ferramenta JFLAP: http://www.jflap.org/);

Todos os arquivos fonte;

Relatório técnico contendo explicações do propósito de todas as classes, métodos ou funções da implementação, assim como testes realizados com programas corretos e errados (no mínimo, 3 certos e 3 errados). Os programas testes deverão ser definidos de acordo com a gramática do PasC. Os resultados deverão apresentar a saída do Analisador Léxico (a sequência de tokens identificados e o local de sua ocorrência) e os símbolos instalados na Tabela de Símbolos, bem como os erros léxicos encontrados.


1.3 Regras

Não é permitido o uso de ferramentas para geração do analisador léxico.

A implementação deverá ser realizada em uma das linguagens C, C++, C#, Java, Ruby ou Python.

A recuperação de erro deverá ser em Modo Pânico. Mensagens de erros correspondentes devem ser apresentadas, indicando a linha e coluna de ocorrência do erro.



4.2 Gramática da linguagem PasC
prog        → “program” “id” body
body        → decl-list “{“ stmt-list “}”
decl-list  → decl “;” decl-list | ε
decl        → type id-list
type        → “num” | “char”
id-list    → “id” | “id” “,” id-list

stmt-list  → stmt “;” stmt-list | ε
stmt        → assign-stmt | if-stmt | while-stmt | read-stmt | write-stmt
assign-stmt → “id” “=” simple_expr
if-stmt    → “if” “(“ condition “)” “{“ stmt-list “}” |
              “if” “(“ condition “)” “{“ stmt-list “}” “else” “{“ stmt-list “}”
condition  → expression
while-stmt  → stmt-prefix “{“ stmt-list “}”
stmt-prefix → “while” “(“ condition “)”
read-stmt  → “read” “id”
write-stmt  → “write” writable
writable    → simple-expr | “literal”

expression  → simple-expr | simple-expr relop simple-expr
simple-expr → term | simple-expr addop term
term        → factor-a | term mulop factor-a
factor-a    → factor | “not” factor
factor      → “id” | constant | “(“ expression “)”
relop      → “==” | “>” | “>=” | “<” | “<=” | “!=”
addop      → “+” | “-” | “or”
mulop      → “*” | “/” | “and”
constant    → “num_const” | “char_const”
4.3 Padrões para números, caracteres, literais e identificadores do PasC
digit      = [0-9]
letter    = [A-Z | a-z]
id        = letter (letter | digit)*
literal    = pelo menos um dos 256 caracteres do conjunto ascii entre aspas duplas
char_const = um dos 256 caracteres do conjunto ascii entre aspas simples
num_const  = digit+ (“.” Digit+)?
4.4 Nomes para os tokens
Operadores:
    OP_EQ: ==  OP_GE: >=  OP_MUL: *
    OP_NE: !=  OP_LE: <=  OP_DIV: /
    OP_GT: >    OP_AD: +    OP_ASS: =
    OP_LT: <    OP_MIN: - 
Símbolos:     
    SMB_OBC: {  SMB_COM: , 
    SMB_CBC: }  SMB_SEM: ; 
    SMB_OPA: (     
    SMB_CPA: )     
Palavras-chave: KW: program, if, else, while, write, read, num, char, not, or, and

Identificadores: ID

Literal: LIT

Constantes: CON_NUM: num_const e CON_CHAR: char_const

4.5 Outras características de PasC
As palavras-chave de PasC são reservadas;

Toda variável deve ser declarada antes do seu uso;

A linguagem possui comentários de mais de uma linha. Um comentário começa com “/*” e

deve terminar com “*/”;

A linguagem possui comentários de uma linha. Um comentário começa com “//”;

A semântica dos demais comandos e expressões é a tradicional do Pascal, exceto que “=” é utilizado no comando de atribuição, “==” é operador relacional que verifica se os operandos são iguais, e “!=” é operador relacional que verifica se os operandos são diferentes;

Os tipos numeral e caractere não são compatíveis;

A linguagem não é case-sensitive;

Cada tabulação, deverá contar como 3 espaços em branco;


Parte II – Análises Sintática e Semântica(extra)

Descrição do trabalho

Análise Sintática:

Nesta etapa, você deverá implementar um analisador sintático descendente (top-down) para
a linguagem PasC, cuja descrição encontra-se no enunciado I.


Seu analisador sintático deverá ser um analisador de uma única passada. Dessa forma, ele deverá
interagir com o analisador léxico para obter os tokens do arquivo-fonte. Você deve implementar seu
analisar sintático utilizando o algoritmo de Parser Preditivo Recursivo baseando-se na Tabela

Preditiva, sem implementá-la, ou o algoritmo de Parser Preditivo Não-Recursivo, implementando
ou baseando-se na Tabela Preditiva e implementando a Pilha.


O analisador sintático deverá reportar o primeiro erro ocorrido no programa-fonte e abortar a
compilação. O analisador deverá informar qual o erro encontrado e sua localização no arquivo fonte.

..

É Possível tratar o modo pânico na recuperação de erros sintáticos construindo os
métodos synch() e skip(). Você deverá construir esses dois métodos conforme visto em sala para que
o modo pânico gere “menos confusão” ao Parser. Lembre-se que a implementação desses métodos
varia conforme o Parser adotado.
S e o número de erros ultrapassar o limite de 3 erros (sintáticos), o
programa deverá abortar a análise.

O algoritmo de Parser Preditivo Não-Recursivo (Tabela Preditiva e Pilha) é mais
desafiador para implementar. Caso o grupo opte por implementá-lo e se estiver com as
funcionalidades corretas, serão atribuídos +4 pontos extras para o grupo.

Análise Semântica: Nesta etapa, você deverá implementar um analisador
semântico de acordo com a árvore sintática produzida pelo Parser descendente (top-down) para a
linguagem PasC.

Seu compilador deverá ser um analisador de uma única passada. Dessa forma, deverá haver
interação entre as analises léxica, sintática e semântica, ao obter os tokens do arquivo-fonte. Você
deve implementar seu analisador semântico utilizando as regras semânticas que são apresentadas na
gramática do PasC.


O analisador semântico deverá reportar possíveis erros ocorridos no programa-fonte, informando
qual o erro encontrado e sua localização no arquivo-fonte. Não há recuperação de erro para análise
semântica. Quando um erro é detectado, um tipo ‘erro’ é repassado para outras operações.
A
identificação dos erros Léxicos e Sintáticos continuam de acordo com as descrições anteriores, isto
é, deverão ser identificados, sinalizados e com recuperação de erro funcional. Use uma “tag” para
classificar/diferenciar erro Léxico, Sintático e Semântico na impressão dos erros.

As verificações semânticas, são de acordo com as regras semânticas, que asseguram:

• Toda variável deve ser declarada antes do seu uso;

• Operações aritméticas (“+”, “-”, “*” e “/”) são realizadas somente com números e resultam
em um tipo númerico;

• Operações de comparação (“==”, “>=”, “<=”, “>”, “<” e “!=”) e operações lógicas (“and” e
“or”) resultam em um tipo lógico;

• Operações lógicas com “and” e “or” devem ter operadores de tipo lógico, já as operações
relacionais devem ter operadores de tipo numérico;

• As expressões condicionais nos comandos “if” e “while” devem resultar em tipo lógico;

• O comando “write” aceita somente tipos numérico ou char;

• O comando de atribuição deve ter compatibilidade entre o “id” e o tipo da expressão;

• O comando “not” opera sobre uma expressão de tipo lógico.
Portanto, para assegurar essas verificações semânticas, você deve implementar as regras semânticas.

O atributo usado é “t”, representando o “tipo” e que pode ter os valores “num”, “char”,
“bool”, “void” e “erro”. O tipo “void” apenas informa que não estamos interessados em um
tipo específico, já o tipo “erro” indica que um erro semântico aconteceu.