[cpl] [Tema 1] Substring in dispatch

[Călin Cruceru]

Salut,

M-am gândit foarte mult la problema aceasta și nu am găsit răspunsul.
Am vorbit și cu foarte mulți colegi și niciunul nu a reușit să facă să
parseze expresia pe care o dădusem eu exemplu în e-mailul inițial.
Câteva comentarii mai jos.

2016-10-27 8:40 GMT+03:00 Bogdan Nitulescu via cpl <cpl at cursuri.cs.pub.ro>:
> Salut,
>
> Exista mai multe locuri in limbaj unde este folosita structura [ ]  :
> virtual method dispatch, substring, array index. Toate sunt expresii, si
> pentru fiecare din ele avem mai multe posibilitati in limbaj:
>
> dispatch, diverse forme:
>     [ <expression>::<identifier>.<identifier> <expression>, ... ,
> <expression>]
>     [ <expression>.<identifier> <expression>, ... , <expression>]
>     [<identifier> <expression>, ... , <expression>]
>
> substring: <expression> [<expression>,<expression>]
> array index: <expression>[<expression>]
>
> Constructiile nu introduc ambiguitati. Static dispatch ('[a::b.c d]') si
> object dispatch ('[a.b c]') sunt suficient de distincte pentru ca au tokeni
> specifici, "::" si "." , ce nu apar altfel intre "[ ]" .
>
> Ramane sa poti distinge intre a[x] - vector ; a[x,y] - substring; si [a x] -
> self dispatch. Aici te ajuta o alta restrictie din limbaj - un dispatch '[a
> x]' trebuie sa inceapa neaparat cu un identificator; deci, daca esti in
> contextul in care este asteptata o expresie si intalnesti '[a[x]]' , dupa ce
> ai parsat '[' ai neaparat un dispatch catre metoda 'a', cu parametrul
> expresia '[x]' ; si nu poti avea un array index 'a[x]'.
>

Eu văd 2 probleme aici:
1. de ce după ce am parsat '[' am neapărat dispatch către 'a'?  Ar
putea urma la fel de bine [a [ x].metoda] (am delimitat lookaheadul),
care nu este self-dispatch, ci dispatch-ul 'metoda' pe expresia
'a[x]'.
2. de ce nu poți avea array index 'a[x]'?  Ce e greșit cu a[b[c[d[x]]]]?

> Un parser LR se descurca sa faca diferenta intre "[a[x].a x]" unde dupa "["
> urmeaza o expresie; si "[a a[x]]" unde dupa "[" urmeaza un identificator,
> pentru ca va face SHIFT intotdeauna si va face REDUCE mai tarziu.
> Intr-adevar, un LL simplu nu ar putea.
>

Am observat că nu ați specificat *ce* parser LR (mă refer la
lookahead), dar eu susțin că nu poți face această diferență decât cu
LR(*) și nu poți face asta cu LR(k), oricât ar fi k.  Pe de altă parte
nu înțeleg ce înseamnă că va face reduce *mai târziu*.  Credeam că
asta e esența parserelor LR(k), ca într-o stare oarecare, având stiva
și k tokeni lookahead, să decidă ce face: aplică o producție pe un
număr anume de elemente din vârful stivei, sau face shift, iar ce e pe
stivă *nu* se mai modifică (și aici nu mă refer la pop, pop.. etc,
urmat de reduce; mă refer că dacă face shift, atunci pentru a face
reduce la un moment ulterior, în partea dreapta a regulei care se va
aplica atunci va trebui să apară *fix* cum a fost lăsat acum pe
stivă).

Iar un exemplu la care m-am gândit că ilustrează ce tocmai am spus
este următorul:

[a[a[a[a[a[a[a[a[a[a[ .... index]]] ... ].metoda]

Asta, conform gramaticii este o expresie validă (și există exemplu
analog cu substring), iar oricâți tokeni lookahead am avea, putem să
mai adăugăm un nivel de indexare și să o facem neparsabilă => merge
doar cu LR(*).  Care e problema aici?

> Hint: gramatica din bison nu trebuie sa fie neaparat pe aceeasi structura pe
> care se genereaza AST-ul (arborele de derivare si cel sintactic pot fi
> diferiti). In plus, daca ai conflict SHIFT REDUCE dar stii sa il rezolvi,
> poti folosi reguli implicite de precendenta, atat timp cat documentezi
> alegerea lor.
>

Mulțumesc,
Călin