ESAME

data una grammatica mostrare che e riconoscibile per mezzo di $LL(1)$

GRAMMATICA

• $S\to dSAB|BC$
• $A\to aA|C$
• $B\to bB|ϵ$
• $C\to c$

PUMPING LEMMA PER DIMOSTRARE CHE NON E DI TIPO 3

si dimostra per mezzo della stringa $d^{n}c{c}^n$ in cui non e identificabile il pezzo centrale per effettuare la scomposizione nei tre pezzi $xwy$ in quanto il pezzo centrale ripetuto non e in grado di generare le due parti della stringa

si vedeva subito anche dal fatto che la prima regola di produzione presenta self embedding e il corrispondente automa a stati finiti avrebbe avuto infiniti stati

CALCOLO DEI DIRECTOR SYMBOLS SET

• $DSS(S->dSAB)=\{d\}$

• $DSS(S->BC)=\{c,b\}$

• $DSS(A->aA)=\{a\}$

• $DSS(A->c)=\{c\}$

• $DSS(B->bB)=\{b\}$

• $DSS(C->c)=\{c\}$

• aggiungere una regola di ricorsione sinistra e mostrare che la grammatica non e più $LL(1)$

• $C\to Cd$

si ha un conflitto nei director symbol set che riguardano il metasimbolo $C$ dato che si ha $DSS(C\to c)$ non disgiunto con $DSS(C\to Cd)$ la grammatica non e $LL(1)$

mostrare che la ricorsione sinistra si può rimuovere ma si ottiene una grammatica diversa

RIMOZIONE DELLA RICORSIONE SINISTRA

• $S\to dSAB|BC$
• $A\to aA|C$
• $B\to bB|ϵ$
• $C\to c|cD$
• $D\to d|dD$

La ricorsione sinistra e rimovibile ma si ottiene una grammatica diversa, non ottimale in caso si voglia applicare una semantica

tentare l’approccio con analisi $LR(0)$ e $SLR$ per verificare se si può mantenere la ricorsione sinistra senza modificare il linguaggio

CALCOLO DEI CONTESTI SINISTRI

• $LEFTCTXLR(0)(Z)=\{ϵ\}$
• $LEFTCTXLR(0)(S)=LEFTCTXLR(0)(Z),LEFTCTXLR(0)(S)d$
• $LEFTCTXLR(0)(A)=LEFTCTXLR(0)(S)dS,LEFTCTXLR(0)(A)a$
• $LEFTCTXLR(0)(B)=LEFTCTXLR(0)(S)dSA,LEFTCTXLR(0)(S),LEFTCTXLR(0)(B)b$
• $LEFTCTXLR(0)(C)=LEFTCTXLR(0)(A),LEFTCTXLR(0)(C),LEFTCTXLR(0)(S)B$

CALCOLO DEI CONTESTI LR(0)

• $CTXLR(0)(Z\to S)=ϵ$
• $CTXLR(0)(S\to dSAB)=d^{\ast }dSAB$
• $CTXLR(0)(S\to BC)=d^{\ast }BC$
• $CTXLR(0)(A\to aA)=(d^{\ast }dS)a^{\ast }aA$
• $CTXLR(0)(A\to C)=(d^{\ast }S)a^{\ast }C$
• $CTXLR(0)(B\to bB)=(d^{\ast }dSA+d^{\ast })b^{\ast }bB$
• $CTXLR(0)(B\to ϵ)=(d^{\ast }dSA+d^{\ast })b^{\ast }$
• $CTXLR(0)(C\to c)=((d^{\ast }S)a^{\ast }+d^{\ast }B{)}^{\ast }c$
• $CTXLR(0)(C\to Cd)=((d^{\ast }S)a^{\ast }+d^{\ast }B{)}^{\ast }Cd$

La grammatica in questione non risulta essere lr(0) in quanto la regola di produzione $B\to ϵ$ genera un conflitto shift/reduce nell’automa

per essere $LR(0)$ non devono esserci ricorsioni destre del tipo $A\to aA|a$ ne produzioni dello stesso metasimbolo che iniziano con la stessa forma di frase e si differiscono per un terminale $S\to B|Ba$, neanche le produzioni della forma $B\to bB|ϵ$ sono corrette in quanto generano nel automa conflitti shift/reduce per via dell $ϵ$-mossa

CALCOLO DEGLI INSIEMI $FOLLO{W}_1$

• $FOLLO{W}_1(S)=END,a,c$
• $FOLLO{W}_1(A)=b,END,$
• $FOLLO{W}_1(B)=c,END,$
• $FOLLO{W}_1(C)=d,END$

e i conseguenti contesti $SLR$

• $SLR(1)CTX(Z\to S)=ϵ$
• $SLR(1)CTX(S\to aSAB)=d^{\ast }dSAB(END+a+c)$
• $SLR(1)CTX(S\to BC)=d^{\ast }BC(END+a+c)$
• $SLR(1)CTX(A\to aA)=(d^{\ast }dS)a^{\ast }aA+aA))(b+END)$
• $SLR(1)CTX(A\to C)=a^{\ast }a(SC+C)(b+END)$
• $SLR(1)CTX(B\to bB)=(a^{\ast }aSA+a^{\ast }+b^{\ast })bB(c,END)$
• $SLR(1)CTX(B\to ϵ)=(a^{\ast }aSA+a^{\ast }+b^{\ast })(c,END)$
• $SLR(1)CTX(C\to c)=((a^{\ast })B+aS{)}^{\ast }c(c+END)$
• $SLR(1)CTX(C\to Cd)=((a^{\ast })B+aS{)}^{\ast }Cd(c+END)$

La grammatica risulta essere $SLR$

COSTRUTTO lesect

costrutto per eseguire una data azione su tutti gli elementi di un array uguali a un dato target

lesect(oggetto_da_iterare,target){funzione da svolgere sull'oggetto}

SCALA

def lesect[T](a:Iterable[T],t:T)(expr:(T) =>Unit):Unit={
	if (!a.isEmpty){
		if (a.head == t) expr(a.head)
		lesect(a.drop(1),t)(expr)
	}
}
//il chiamante puo sfruttare la block like sintax e il costrutto e completato
val a=Array("a","b","b")
lesect(a,"b"){print}

JAVASCRIPT

function lesect(iterable,target){
  return function(expr){
    if (iterable.length!==0){
      if (iterable[0] === target){expr(iterable[0])}
      lesect(iterable.slice(1),target)(expr)
    }
  }
}
 
var a=Array("a","b","b")
lesect(a,"a")(console.log)
lesect(a,"b")(console.log)
lesect(a,"c")(console.log)

IL CACCIAVITE DEL SISTEMISTA (grep DEI POVERI)

con il potentissimo costrutto lesect e la possibilità offerta da javascript di costruire funzioni dinamicamente si possono ricreare molti tool unix semplicemente modificando un file,

const readline = require('readline');
const lesect = require('./lesect.js')
const fs = require('node:fs');
 
// check sui parametri
if (process.argv.length<4){console.error("wrong parameters"); process.exit(1)}
 
try {
  var commandfile=process.argv[2]
  var target=process.argv[3]
  const commandBody = fs.readFileSync(commandfile, 'utf8');
  var commmand= Function("x",file)
  var lines = [];
  
  var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal:false
  });
 
  rl.on('line', (line) => {
    lines.push(line);
  });
  // approssimazione pessima, in questo modo non si consuma input prima di averne concluso la lettura, crash assicurato
  rl.on('close', (line) => {
    lesect(lines,target)(command)
  });
 
} catch (err) {
  process.exit(1)
}

e cosi possibile cambiare la semantica del costrutto lesect a runtime per mezzo di un semplice file javascript

• con questo lesect emula grep

console.log

• con questo emula il comando replace di sed

console.log(x.replace(process.argv[3],process.argv[4]))

esempi di chiamate

echo -e "a\nb\nb" | node mktool.js poorgrep.txt b
echo -e "a\nb\nb" | node mktool.js poorsed.txt a c

TRATTI DI SCALA: LE REVERSE PIPES

mostrare come scala risolve il problema dell’ereditarietà multipla per mezzo dei tratti, e le limitazioni dei tratti parametrici

// GIRA SOLO SU SCALA 3, TESTARE QUI https://scastie.scala-lang.org
class Pipe(var input:String){
	def run():Unit={
		print(input)
	}
}
trait grep(regex:String) extends Pipe{
  override def run():Unit={
    input= input.split("\\\\n").filter((x)=>{x.contains(regex)}).toList.mkString("\n");
    super.run();
  }
}
trait sed(regex:String,replace:String) extends Pipe{
  override def run():Unit={
    input= input.split("\\\\n").toList.map(x => x.replaceAll(regex,replace)).mkString("\n");
    super.run();
  }
}
(new Pipe("hello world")  with grep("pippo") with sed("hello","pippo") ).run()

non e possibile creare reverse pipes con comandi ripetutu perche perche un tratto parametrico se esteso due volte con parametro non puo essere linearizzato

class PipeGrepSed extends Pipe("Hello world") with grep("pippo") with sed("hello","pippo")
class PipeGrepSedGrep extends PipeGrepSed with grep("world")

questo non compila perche la seconda classe cerca di richiamare il costruttore del tratto grep() che viene già chiamato dalla classe padre