Start presentation

Slide 1: Terminologia e Retroterra

• Linguaggio, Grammatica e descrizione

• Definizione comune: Sistema di comunicazione tra individui

Le parti di questo sistema

• Le frasi,
• le parole
• l'alfabeto

La comunicazione coinvolge il significato informazione=significato

Slide 2: Linguaggio Definizione

• Insieme infinito di una sequenza di frasi
• la struttura \xE8 l'insieme di regole sulla combinazione delle frasi
• una frase \xE8 una sequenza di "atomi" non ulteriormente decomponibili chiamati token

Slide 3: Sintassi, grammatica

Nel linguaggio comune sintassi/grammatica e' duale di frase/parola

• sintassi regola la struttura della frase
• grammatica regola la struttura della parola

Parola come Linguaggio

• alfabeto elemento base
• parola come frase

Slide 4: Grammatica Definizione

• " ... a grammar is any exact, finite-size, complete description (NdR) of the language, i.e., of the set of sentences. This is in fact the school grammar, with the fuzziness removed......." 1

Grammatica Generativa

* "... generative grammar is an exact, fixed-size recipe (NdR algoritmo) for constructing the sentences in the language. This means that, following the recipe, it must be possible to construct each sentence.." 1

Domanda

• Tutti i Linguaggi possono avere una descrizione generativa?
• NO l'insieme delle descrizioni" \xE8 numerabile mentre quello dei linguaggi ha la potenza del reale

Slide 5: Token e non Terminal symbol

• Token (terminal symbol), cio\xE9 elementi base del linguaggio non ulteriormente scomponibili realmente
• non-Terminal ( sottoinsiemi del linguaggio )

Definizione Grammatica Generativa

• V_T un insieme di elementi terminali (token) [a,\,b,\,, \alpha \cdots
• V_N un insieme di elementi non terminali
• per non creare confusione V_N \cap V_T=\emptyset
• una funzione R , o pi\xF9, che ha come dominio l'insieme unione T=V_N \cup V_T e come codominio lo stesso insieme T=V_N \cup V_T
• il simbolo di partenza S \in V_N

Slide 6: Classificazione delle Grammatiche Generative (1)

• Le funzioni R\, : \, A \alpha \rightarrow \beta \alpha \gamma caratterizza la grammatica e quindi il linguaggio
• la classificazione viene fatta defininendo la tipologia di R associata ad una certa grammatica
• 4 livelli di grammatica
• Le funzioni vengono descritte da regole (o uguaglianze)

Grammatica Tipo 1

• La relazione \xE8 tale che il suo membro di sinistra non contiene pi\xF9 elementi del suo membro di destra
• oppure l'applicazione della regola \xE8 vincolata al contesto quindi le sostituzioni ricorsive debbono essere fatte una alla volta

Slide 7: Classificazione delle Grammatiche Generative (2)

Grammatica Tipo 2 Context Free (CF)

• Grammatica non vincolata al contesto
• solo un non-terminale nel membro di sinistra

Bakus-Nauer Form for CF Grammar

• < some text > per non terminali
• ::= per "produce"
• | per "oppure

Slide 8: Classificazione delle Grammatiche Generative (3)

Grammatica Tipo 3

• Solo un non terminale nel membro destro.

Grammatica Tipo 4

• nessun non-terminale nel membro di destra (generazione di parole)

Slide 9: Bison

• Grammatica di tipo Context-Free
• Parsing LALR(1)

Slide 10: Bison Grammar File

• Prologue

%{
Prologue
%}

• Directive

%token ......

• Grammar Rule According to BNF

%%
expr:      NUMBER  
| expr '+' expr    { code(add); };
%%

Slide 11: Prologue

• Inclusione di direttive necessarie per la esecuzione della parte semantica

%{
#define _GNU_SOURCE
#include <stdio.h>
#include "ptypes.h"
%}

• i token possono contenere tipologie di dati diversi (es. variabile o costante) \xE8 necessario definire una struttura dati che possa contenerli

%union {
long int n;
tree t; /* tree is defined in 'ptypes.h' */
}

Slide 12: DIrective

• symbol, terminal, non terminal

Terminal

• token elemento atomico
• "A terminal symbol (also known as a token type) represents a class of syntactically equivalent tokens." [[#RefN2][2]
• "A character token type (or literal character token) is written in the grammar using the same syntax used in C for character constants; for example, '+' is a character token"[[#RefN2][2]

Slide 13: nonTerminal

• "A nonterminal symbol stands for a class of syntactically equivalent groupings. "[[#RefN2][2]

Slide 14: Symbols

Slide 15: Action

• All'interno di parentesi graffe il codice C che sar\xE0 eseguito nel caso la regola grammaticale risulti soddisfatta.

exp:
       ...
      | exp \x92+\x92 exp
      { $$ = $1 + $3; }

Slide 16: Analizzatore grammaticale

Slide 17: Macchina Stack

Reference

[1] DICK GRUNE, CERIEL JACOBS, "PARSING TECHNIQUES A Practical Guide", Printout by the Authors Vrije Universiteit, Amsterdam, The Netherlands

[2] Charles Donnelly and Richard Stallman, Bison, 2010, Free Software Foundation, Inc.

-- RobertoBernetti - 03 Mar 2011