Sintaxe de uma Linguagem

  • Published on
    22-Jan-2016

  • View
    31

  • Download
    0

Embed Size (px)

DESCRIPTION

Sintaxe de uma Linguagem. Especificada atravs de uma gramtica livre de contexto, BNF (Backus-Naur Form). Vantagens de usar uma gramtica. Uma gramtica d uma especificao precisa e fcil de entender da sintaxe de uma linguagem de programao - PowerPoint PPT Presentation

Transcript

  • Sintaxe de uma LinguagemEspecificada atravs de uma gramtica livre de contexto, BNF (Backus-Naur Form).

  • Vantagens de usar uma gramticaUma gramtica d uma especificao precisa e fcil de entender da sintaxe de uma linguagem de programaoPara algumas classes de gramticas, possvel gerar automaticamente um parser eficiente. Alm disso as ferramentas usadas indicam ambiguidades e outras construes difceis de serem reconhecidas e que passaram desapercebidasTem relao direta com a estrutura da linguagem usada para traduo/compilao.Fcil de ser estendida/atualizada.

  • Analisador Sinttico - ParserAnalisador lxicoparserpede prximo tokenPrograma fontetokentabela de smbolosParse treeResto do front-endRepresentao intermediria

  • Tipos de parsers para gramticasMtodos de parsing universais: funcionam para qualquer gramtica, mas so muito ineficientes (inviveis para uso prtico).Top down: constroem as parse trees a partir da raiz em direo s folhas.Bottom-up: constroem as parse trees a partir das folhas.

  • Parsers top-down ou bottom-upEm parsers top-down ou bottom-up a leitura do arquivo sempre feita da esquerda para a direita, um smbolo de cada vez.S funcionam para um subconjunto de gramticas, que na prtica so suficientes para a grande maioria das linguagens de programao.

  • Tratamento de Erros de SintaxeRelatar presena de erros claramente e com precisoRecuperar-se do erro rapidamente, para possibilitar a deteco de erros subsequentesNo deve gerar overhead significativo para programas corretos.

  • Gramticas Livres de Contextostmt g if expr then stmt else stmt Um conjunto de smbolos terminais (tokens). Um conjunto de smbolos no-terminais (variveis).Um conjunto de produes, cada produo consiste de um no-terminal. Uma seta, e uma seqencia de tokens e/ou no terminaisUm no terminal designado como smbolo inicial

  • Exemplo 1expr g expr op expr expr g ( expr ) expr g - expr expr g id op g + op g - op g * op g / op g ^

  • Exemplo 1 (notao abreviada)expr g expr op expr | ( expr ) | - expr | id op g + | - | * | / | ^

  • Exemplo 2 block g begin op_stmts end op_stmts g stmt_list | stmt_list g stmt_list ; stmt | stmt

  • Parse TreesMostra graficamente como o smbolo inicial de uma gramtica deriva uma string da linguagem.Para uma produo A g XYZ ZAXY

  • AmbiguidadeParse-tree gera uma string, mas uma string pode possuir vrias parse-trees, se a gramtica for ambgua.Soluo: usar sempre gramticas no-ambguas, ou gramticas ambguas com informaes adicionais sobre como resolver ambiguidades.

  • Ambiguidade - Exemplo

    E g E + E | E * E | - E | ( E ) | id

  • Exemplo: Duas parse treesid + id * id

    EEEEE+*idididEEEEE+*ididid

  • Expresses Regulares x Gramticas Livres de ContextoTudo que pode ser descrito por uma expresso regular pode ser descrito com gramticas livres de contexto, mas:As regras lxicas so especificadas mais simplesmente com expresses regularesExpresses Regulares geralmente so mais concisas e simples de entenderPodem ser gerados analisadores lxicos mais eficientes a partir de expresses regularesEstrutura/modulariza o front-end do compilador

  • Exemplo(a | b)*abbA0 g aA0 | bA0 | aA1 A1 g bA2 A2 g bA3 A3 g

  • Expresses Regulares x Gramticas Livres de ContextoExpresses regulares so convenientes para especificar a estrutura de construes lxicas, como identificadores, constantes, palavras chave etc.Em geral usa-se gramticas para especificar estruturas aninhadas, como parenteses, begin-end, if-then-else etc.

  • Eliminando Ambiguidadesstmt g if expr then stmt | if expr then stmt else stmt | other if E1 then S1 else if E2 then S2 else S3if E1 then if E2 then S1 else S2Nas linguagens de programao normalmente a regra que o else casa com o then mais prximo.

  • Soluostmt g matched_stmt | unmatched_stmtmatched_stmt g if expr then matched_stmt else matched_stmt | otherunmatched_stmt g if expr then stmt | if expr then matched_stmt else unmatched_stmt

  • Recurso EsquerdaUma gramtica recursiva esquerda se existe um no terminal A tal que existe uma derivao de A que gera A, para alguma string .Existem tcnicas/algortimos para eliminar a recurso esquerda.

  • Recurso Esquerda - exemplosA g A | pode ser substituido por A g A A g A | E g E + T | T pode ser substituido por E g TE E g +TE |

  • Fatorao EsquerdaTcnica de transformao de gramtica usada para produzir uma gramtica adequada para predictive parsing.Combina os casos em que h mais de uma alternativa possvel a partir do reconhecimento de um token.Existem tcnicas/algortimos para fazer a fatorao esquerda.

  • Fatorao Esquerda - exemplostmt g if expr then stmt | if expr then stmt else stmt stmt g if expr then stmt stmt stmt g else stmt |

  • Construes que no podem ser especificadas por gramticas livres de contextoL = {wcw | w est em (a|b)*} ex: declarao de variveis antes de seu usoL = {anbmcndm | n >= 1 e m >= 1} ex: contagem do nmero de argumentos de funes/procedimentos.

  • Parsers top-downRecursive-descent parsing: tcnica de parsing top-down que suporta backtrackingpredictive parsing: recursive-descent parsing sem backtracking.Relativamente fceis de escrever moS reconhecem alguns tipos de gramticas: no suportam recurso esquerda, precisa fazer fatorao esquerda (predictive).

  • Parsers top-downExemplo: reconhecer stmt g if expr then stmt else stmt | while expr do stmt | begin stmt_list endPode fazer uso na implementao de diagramas de transio, ou ser implementado recursivamente.

  • Parsers bottom-upTambm chamado de shift-reduce parsing reduz uma string w ao smbolo inicial da gramtica. A reduo ocorre atravs da substituio do lado direito de uma produo pelo no-terminal do seu lado esquerdo.Mais complexo, constri a rvore a partir das folhas. Gerado por ferramentas automticas.

  • Parser bottom-up - exemploS g aABe A g Abc | b B g d abbcde aAbcde aAde aABe S

    Cap.4, at seo 4.4.1.*

Recommended

View more >