^^Formal grammar. Linguaggio. Grammatica formale.

1956 Noam Chomsky comprese che

• la sintassi di una proposizione si puo' rappresentare come albero
• le regole per costruire proposizioni sintatticamente corrette si possono scrivere come una definizione induttiva
  (che chiamò grammatica generativa).

Grammars are best introduced by example.

Idea per generare le stringhe

slogan: "da stringa nasce stringa"

1. una stringa durante il procedimento di generazione e' composta da
   • lettere  rimpiazzabili ≡ non-terminali     A, B, C, ... MAIUSCOLE
   • lettere  non-rimpiazzabili ≡ terminali     a, b, c, ...  minuscole

   (Lettere di 2 tipi mutuamente esclusivi, se una lettera e' di un tipo, allora non e' dell'altro.)

2. dalla stringa attuale si generare la stringa seguente:
   una (solo 1) lettera rimpiazzabile viene rimpiazzata secondo una delle regole di rimpiazzo, che possono essere usate in un qualsiasi ordine

   es:  1: A→bA;  2: A→b    da  bbA→bbbA reg1;  bbA→bbb reg2

3. la stringa e' terminata quando nella stringa non ci sono piu' lettere rimpiazzabili poiche' sono state tutte rimpiazzate da lettere terminali.

   La stringa in corso puo' non essere generabile poiche' procedimento:

   • interminabile infinito, es: A→bA  only
   • bloccato: nessuna regola applicabile ad una stringa non terminata.
4. il procedimento di generazione inizia da 1 sola lettera rimpiazzabile, che deve essere indicata, poiche' iniziando da un'altra puo' accadere che vengano generate stringhe diverse.
   Per usanza e' la lettera S, in origine Chomsky  S ≡ Sentence.

G = (N, Σ, P, S)

the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s

G formal grammar    le regole per generare le stringhe del suo linguaggio formale.

1. N nonterminals  simboli da sostituire coi simboli terminali
2. Σ terminals ≡ terminal alphabet ≡ alphabet simboli terminali.

   N e Σ hanno almeno 1 simbolo; non hanno simboli in comune, per escludere equivoco; i simboli sono indivisibili.

3. P productions rules of the form
   α → β   α, β strings of terminals and nonterminals

                α must contain at least 1 nonterminal

4. Esiste almeno una produzione  S → β.
   S start symbol ≡ sentence symbol  a nonterminal, i.e.  S∈N, from which the production begins.
    

language generated by the grammar    all distinct strings that can be generated in this manner.

weak equivalence of two grammars    they generate the same set of strings, i.e. they generate the same formal language.

strong (≡ structural) equivalence    additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both.

Introduced by Chomsky (1963), who argues that only strong equivalence is relevant when comparing grammar formalisms.

Example of formal grammar >>>

Grammars are best introduced by example.

ref: cs.ksu.edu/~schmidt

Use of formal grammar, of formulas of a formal grammar

Two key uses of formulas are in propositional logic and predicate logic.

A formal grammar is a kind of rewriting system

where the alphabet is divided into terminal and nonterminal symbols, and all inference rules are local and involve a nonterminal on the LHS. The computation starts from a specific initial nonterminal and halts when the word contains only terminals. The set of possible resulting words is the language defined by the grammar.

ref: stackexchange/relations-between-formal-systems-rewriting-systems

Vocabolario

1. ≡ rimpiazzabile  en: replaceable
   ≡ riscrivibile       en: rewritable
   ≡ sostituibile      en: substitutable
   ≡ variabile         en: variable
2. ≡ regola di rimpiazzo      en: replacement rule
   ≡ regola di generazione  en: generation rule
   ≡ regola di produzione    en: production rule
   ≡ produzione
   ≡ regola di derivazione    en: derivation rule
   ≡ regola di formazione    en: formation rule
   ref: associazione Regole di derivazione (di una funzione).
3. 1: A → bA    la lettera A   viene sostituita da  bA

   2: A→b        la lettera A   viene sostituita da  b

4. production rule's left-hand side, production rule's right-hand side

Grammatica ambigua

ambiguous grammar  the same string can be generated in essentially different ways.

wp/Ambiguous_grammar

Teo: not every grammar has an unambiguous equivalent.

Non esiste un procedimento generale per riscrivere una grammatica ambigua con una grammatica equivalente e non ambigua.

syntactic ambiguity ≡ structural ambiguity ≡ amphiboly ≡ amphibology

sentence may be interpreted in more than one way due to ambiguous sentence structure.

Syntactic ambiguity arises not from the range of meanings of single words (polysemy), but from the relationship between the words and clauses of a sentence, and the sentence structure underlying the word order therein. In other words, a sentence is syntactically ambiguous when a reader or listener can reasonably interpret one sentence as having more than one possible structure.

wp/Syntactic_ambiguity | Polysemy  semantic ambiguity

Ambiguity#Semantic_and_syntactic_ambiguity

Regola di produzione di una grammatica generativa

Scopo: da una stringa generare una nuova stringa, seguendo le regole

Esempi

1ª produzione: il processo inizia indicando la regola di avvio, che agisce sulla stringa vuota; usualmente la parte sinistra e' cositituita dalla sola lettera S.

Regola di produzione, def

    α → β    struttura

α, β  stringhe di sostituibili e terminaii mischiate in qualsiasi modo e nr

α     ha almeno 1 sostituibile

β     puo' essere stringa_vuota

Uso. In breve: "sostituire la parte sx con la dx", precisamente:

1. trovare nella stringa iniziale una sottostringa uguale alla parte sinistra di una regola di produzione
2. sostituirla con la sua parte destra

nm:

Abbreviare la scrittura delle regole di produzione

Abbreviazione di produzioni con uguale left-hand side

A→a, A→b, ..., A→u    breve    A → a|b|...|u

A→0, A→1, ..., A→9    breve    A → 0|1|2|3|4|5|6|7|8|9

derivation of a string (for a grammar)   a sequence of grammar rule applications that transform the start string into the string.

A derivation proves that the string belongs to the grammar's language.

wp/Derivations and syntax trees (leftmost derivation)

Links

1. rewriting system. Sistemi di riscrittura.
2. wp/production rules for wp/strings

Tipi di grammatica formale

noncontracting_grammar   in ogni regola di produzione

lunghezza parte sinistra ≤  len(parte destra)

ref: wp

Increasing generality of languages:
regular < context-free < context-sensitive < recursively enumerable

Context-free grammar. Context-sensitive grammar.

LR and LL grammar & language

LR  scan left to right, using right reductions

LR(k)   "     "           with k character of lookahead

1965: LR grammars discovered by Knuth.

LL   scan left to right, using left reductions

LL(k)   "     "           with k character of lookahead

LL(1) is important.

1968: LL grammars discovered by Lewis and Stearns.

Links inet

LL_parser | LL_grammar | Leftmost derivation

LR_parser (and grammar)

Bottom-up_parsing ha disegni e confronto con Top-down_parsing

Recursive_descent_parser

Regular_language | Regular_grammar

Deterministic

Deterministic_context-free_language

Deterministic_pushdown_automaton

legati da: i linguaggi accettati da tali automi

Deterministic_context-free_grammar; are unambiguos, ma non coprono tutte le grammatiche anambigue.

State machine. Automaton.

Automa_(informatica) | Automata_theory | Abstract_machine

Automa_a_stati_finiti | Finite-state_machine

Links

1. Linguaggio formale.
2. esOf: Ricorsione matematica. Definizione ricorsiva. Struttura ricorsiva. Induzione matematica.
3. Formal grammar. Backus–Naur form (BNF).
4. Parsing (a string of a language).

Links inet

1. matt.might/grammars-bnf-ebnf The language of languages

Links wikipedia

1. Template: Formal languages, grammars, abstract machines

   1. Formal_language

      • Well-formed_formula

   2. Formal_grammar

      1. Context-free_grammar. Pagina ricca, da leggere.
      2. Chomsky_hierarchy

      3. Chomsky_normal_form

      4. Equivalence_(formal_languages)

      5. Noncontracting_grammar

      6. Ambiguous_grammar

      7. Phrase_structure_grammar

      8. Dependency_grammar

         opencog.org/RelEx_Dependency_Relationship_Extractor

2. Syntax_(programming_languages)

   1. Syntactic_ambiguity

   2. Polysemy  semantic ambiguity

   3. Ambiguity#Semantic_and_syntactic_ambiguity

   4. AST Abstract_syntax_tree

Talk

Production rule of a grammar (def dettagliata)

Prodution rule, structure

left & right side of the production rule are strings

1. done with any letter, order, repetition

   es:  bcaBABad → CcB

2. left-side must always contain a replaceble letter
   es:  bca → CcB    forbidden
3. right-side can be empty

Production rule, use

"replace the left-side with the right-side".

Durante il processo di generazione, nella stringa attuale

1. trovare una sottostringa uguale alla parte sinistra di una regola di produzione
2. sostituirla con la sua parte destra