Compiladores P2

ESCOLA POLITÉCNICA DA UNIVERSIDADE DE SÃO PAULO

Departamento de Engenharia de Computação e Sistemas Digitais

Relatório P2

Compilador

PCS2056 – Linguagens e Compiladores

Bruno Umeda Grisi 5438011

Nathalia Sautchuk Patrício 5432596

 

Índice

1. Definição da Linguagem 3

1.1 Notação BNF 3

1.2 Notação de Wirth 4

2. Análise Léxica 5

3. Análise Sintática 6

3.1 Submáquina Program 6

3.2 Submáquina Expr 6

4. Parte 3 8

1. Definição da Linguagem

A linguagem LazyComb é uma combinação de quatro linguagens: Combinator Calculus (CC), Unlambda, Iota e Jot.

1.1 Notação BNF

Abaixo temos a linguagem em notação BNF:

<Program> ::= <CCExpr>

<CCExpr> ::= <CCExpr> <Expr> | epsilon

<Expr> ::= i | <Expr'>

<IotaExpr> ::= i | <Expr'>

<Expr'> ::= I

| K | k

| S | s

| <NonemptyJotExpr

| ` <Expr1> <Expr2>

| * <IotaExpr1> <IotaExpr2>

| ( <CCExpr> )

<NonemptyJotExpr> ::= <JotExpr> 0

| <JotExpr> 1

<JotExpr> ::= <NonemptyJotExpr> | epsilon

1.2 Notação de Wirth

A partir da notação BNF, criamos a descrição em notação de Wirth abaixo:

Notação de Wirth:

Program = CCExpr .

CCExpr = { Expr } .

Expr = "i" | Expr’ .

IotaExpr = "i" | Expr’ .

Expr’ = "I" | "K" | "S" | "k" | "s" | NonemptyJotExpr | "‘" Expr Expr

| "*" IotaExpr IotaExpr | "(" CCExpr ")" .

NonemptyJotExpr = JotExpr ( "0" | "1" ) .

JotExpr = [ NonemptyJotExpr ] .

Notação de Wirth simplificada:

Program = { Expr }.

Expr = "i" | "I" | "K" | "k" | "S" | "s" | ( "0" | "1") { "0" | "1" } | "`" Expr Expr | "*" Expr Expr | "(" { Expr } ")" .

Notação de Wirth com atenção aos tipos de linguagem que compõe a Lazy-Comb:

Program = { Expr } . #Lazy-Comb

Expr = "i" #CC | Iota

| "I" #CC

| "K" | "k"