O specificare completa a unui limbaj de programare trebuie sa indeplineasca cel putin doua functii. In primul rand trebuie specificata sintaxa limbajului; adica care sunt simbolurile care vor construi programe corecte. In al doilea rand, trebuie specificata semantica limbajului; adica, ce semnificatie trebuie atribuita fiecarui program corect din punct de vedere sintactic.
Un compilator pentru un limbaj de programare trebuie sa verifice daca programul se supune conventiilor sintactice ale specificatiilor limbajului.
De asemenea, trebuie sa traduca fisierul de intrare intr-un fisier scris intr-un cod obiect, intr-un mod consistent in raport cu semantica limbajului.
In plus, daca programul contine erori sintactice, compilatorul ar trebui sa anunte prezenta lor si sa incerce sa indice pozitia lor in codul sursa. Pentru a putea efectua aceste lucruri fiecare compilator are un dispozitiv incorporat, numit analizor.
Pentru a specifica sintaxa unui limbaj de programare se poate folosi o gramatica independenta de context. In plus, daca gramatica este construita cu grija, mare parte din semantica limbajului poate fi exprimata prin regulile gramaticii.
Exista multe tipuri de analizoare pentru gramatici independente de context. In aceasta lucrare vom vorbi doar despre analizoarele LR.
Aceste analizoare sunt eficiente si foarte potrivite pentru compilatoare de limbaje de programare. Poate mai important este faptul ca putem genera automat analizoare LR pentru o gama larga si folositoare de gramatici independente de context. Un aspect important al algoritmului pentru generarea unui analizor este detectarea automata a ambiguitatilor si a bucatilor dificil de analizat din specificatia limbajului.
Mai intai vom arata cum poate o gramatica independenta de context sa defineasca un limbaj. Apoi vom discuta analiza LR si vom evidentia algoritmul de generare al analizorului.
Incheiem prin a arata cum poate fi imbunatatita performanta analizoarelor LR prin cateva transformari simple si cum poate fi incorporata recuperarea erorilor in analiza LR.
In continuare, o secventa de simboluri terminale o vom numi propozitie. Propozitiile sunt scrise intre apostroafe (). De exemplu a, ab, , sunt propozitii.
Propozitia vida este. Doua propozitii scrise una langa alta vor fi concatenate, astfel a b este sinonim cu ab. Termenul de limbaj va insemna aici o multime de propozitii.
Gramatici si arbori de derivare II.
1. Gramatici O gramatica este folosita pentru a defini un limbaj si pentru a impune o structura pentru fiecare propozitie din limbaj. Ne vom ocupa doar de gramaticile independente de context, denumite uneori specificatii BNF (Backus-Naur form). Intr-o gramatica independenta de context specificam doua seturi disjuncte de simboluri pentru a ajuta la definirea unui limbaj. Unul este un set de simboluri neterminale.
Un simbol neterminal va fi reprezentat de o secventa de una sau mai multe litere mari. De exemplu, LIST reprezinta un neterminal, la fel ca si ...
AHO A. V. , DENNING P. J. , ULLMAN J. D. - "WEAK AND MIXED STRATEGY PRECEDENCE PARSING" - J. ACM 19, 2, PAG. 225 - 243, 1972
AHO A. V. , JOHNSON S. C. , ULLMAN J. D. - "DETERMINISTIC PARSING OF AMBIGUOUS GRAMMARS" - CONFERENCE RECORD OF ACM SYMPOSIUM ON PRINCIPLES OF PROGRAMMING LANGUAGES, PAG. 1 - 21, OCT. 1973
AHO A. V. , PETERSON T. G. - "A MINIMUM DISTANCE ERROR - CORRECTING PARSER FOR CONTEXT - FREE LANGUAGES" - SIAM J. COMPUTING 1, 4, PAG. 305 - 312, 1972
AHO A. V. , ULLMAN J. D. - "THE THEORY OF PARSING, TRANSLATION AND COMPILING" - VOL. I, "PARSING", PRENTICE - HALL, ENGLEWOOD CLIFFS, N. J. , 1972
AHO A. V. , ULLMAN J. D. - "OPTIMIZATION OF LR(K) PARSERS" - J. CMPUTER AND SYSTEM SCIENCES 6, 6, PAG. 573 - 602, 1972
AHO A. V. , ULLMAN J. D. - "THE THEORY OF PARSING, TRANSLATION AND COMPILING" - VOL. II, "COMPILING", PRENTICE - HALL, ENGLEWOOD CLIFFS, N. J. , 1973
AHO A. V. , ULLMAN J. D. - "A TECHNIQUE FOR SPEEDING UP LR(K) PARSERS" - SIAM J. COMPUTING 2, 2, PAG. 106 - 127, 1973
ANDERSON T. - "SYNTACTIC ANALYSIS OF LR(K) LANGUAGES" - PHD THESIS, UNIV. NEWCASTLE - UPON - TYNE, NORTHUMBERLAND, ENGLAND, 1972
ANDERSON T. , EVE J. , HORNING J. J. - "EFFICIENT LR(1) PARSERS" - ACTA INFORMATICA 2, PAG. 12 - 39, 1973
DEREMER F. L. - "PRACTICAL TRANSLATORS FOR LR(K) LANGUAGES" - PROJECT MAC REPORT MAC TR - 65, MIT, CAMBRIDGE, MASS, 1969
EARLEY J. - "AN EFFICIENT CONTEXT - FREE PARSING ALGORITHM" - COMM. ACM 13, 2, 94 - 102, 1970
FLOYD R. W. - "SYNTACTIC ANALYSIS AND OPERATOR PRECEDENCE" - J. ACM 10, 3, PAG. 316 - 333, 1963
KNUTH D. E. - "ON THE TRANSLATION OF LANGUAGES FROM LEFT TO RIGHT" - INFORMATION AND CONTROL 8, 6, PAG. 607 - 639, 1965
KNUTH D. E. - "TOP DOWN SYNTAX ANALYSIS" - ACTA INFORMATICA 1, 2, PAG. 97 - 110, 1971
LALONDE W. R. , LEE E. S. , HORNING J. J. - "AN LALR(K) PARSER GENERATOR" - PROC. IFIP CONGRESS 71. TA - 3, NORTH - HOLLAND PUBLISHING CO. , AMSTERDAM, THE NETHERLANDS, PAG. 153 - 157, 1971
LEWIS P. M. , STEARNS R. E. - "SYNTAX DIRECTED TRANSDUCTION" - J. ACM 15, 3, PAG. 464 - 488, 1968
MCKEEMAN W. M. , HORNING J. J. , WORTMAN D. B. - "A COMPILER GENERATOR" - PRENTICE - HALL, ENGLEWOOD CLIFFS, N. J. , 1970
PAGER D. - "A FAST LEFT - TO - RIGHT PARSER FOR CONTEXT - FREE GRAMMARS" - TECHNICAL REPORT PE 240, INFORMATION SCIENCES PROGRAM, UNIV. HAWAII, HONOLULU, HAWAII, 1972
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
