Benzer yapıların kaynak kodu ayrıştırma ve makro benzeri işleme

Question

TL; DR VERSİYONU: ​​Aşağıdakileri destekleyen bir çözümleyici üreteci var mı: bazı kurallar azaldığında (LALR (1) ayrıştırıcı varsayalım), azaltma gerçekleştirilmez. ancak ayrıştırıcı, bu kuraldaki değerleri kullanarak girdiyi farklı kodla değiştirir ve değiştirir ve bu kodu ayrıştırır. Gerekirse tekrarlayın.

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)" 

Yani temelde kod yeniden yazma makroları kullanarak: Kod "i ++" ve kural "expr POST_INCR" Yani, eğer ben daha fazla veya daha az yapabilirim?

UZUN VERSİYON:

I (basitlik için Java) bir başka basit yorumlanır dili yazdım. Tamam çalışıyor, ama bazı soruları gündeme getirdi. Giriş oldukça uzun, ancak basit ve sorunumu açıkça göstermeye yardımcı oluyor (bence).

"while" döngüsüne sahibim. Bu göz önüne alındığında, oldukça basittir:

new WhileNode(boolean_expression, statement); 

Bu sonradan ziyaret ettiğinde, benim sanal makine için kod üretir, yeni bir düğüm oluşturur:

WHILE LPARE boolean_expression RPAREN statement 

aşağıdaki az ya da çok üretir. Bu Oluşturduğum yukarıda belirtilen kurala Java'ya veya C'den bilinen "döngü" aşağı yukarı takip ediyor

FOR LPAREN for_init_expr SEMICOLON boolean_expression SEMICOLON for_post_expr RPAREN statement 

: Ama aynı zamanda şu var

new ListNode(
    for_init_expr, 
    new WhileNode(
     boolean_expression, 
     new ListNode(
      statement, 
      new ListNode(for_post_expr, null)))) 

Bu elbette basit dönüşümdür dan:

for (for_init ; boolean_expression ; for_post_expr) 
    statement 

için:

for_init 
while (boolean_expression) { 
    statement 
    for_post_expr; 
} 

Tüm iyi, güzel, ama işler aşağıdakiler için kıllı olsun: iyi bilinen ve sevdiysen

FOR LPAREN var_decl COLON expression RPAREN statement 

This:

for (int x : new int[] { 1, 2 }) 
    print(x); 

Ben AST üretir kod yayınlamaktan kaçının döngü temel beri, Zaten biraz uzun oldu, ve buraya geldiğimiz daha da kötü. Bu yapı eşittir:

int[] tmp = new int[] { 1, 2 }; 
for (int it = 0 ; it < tmp.length; it = it + 1) { 
    int x = tmp[it]; 
    print(x); 
} 

Ve türlerini kullanarak değilim çünkü ben sadece "ifadesi" (çok doğru tarafı KOLON sonra) ben adımlayabilirsiniz şey olduğunu varsayalım (ve diziler iterable değildir), Iterable örneğini döndüren bu "ifade" nin bir sonucu olarak adlandırıyorum. Yani, aslında, benim yeniden yazılmış kod, yukarıdaki gibi basit değildir az ya da çok bu:

Iterator it = makeIterable(new int[] { 1, 2 }); 
while (it.hasNext()) { 
    int x = it.next(); 
    print(x); 
} 

O OLDUĞUNU kötü görünüyor, ama bunun için o AST üç fonksiyon çağrıları ve süre üretir dikkat etmez döngü.

113  | FOR LPAREN var_decl_name.v PIPE simple_value_field_or_call.o RPAREN statement.s 
114           {: Symbol sv = ext(_symbol_v, _symbol_o); 
115           String autoVarName = generateAutoVariableName(); 
116           Node iter = new StatementEndNode(sv, "", 
117            new BinNode(sv, CMD.SET, "=", 
118             new VarDeclNode(sv, autoVarName), 
119             new CallNode(sv, "()", 
120              new BinNode(sv, CMD.DOT, ".", 
121               new MkIterNode(sv, o), 
122               new PushConstNode(sv, "iterator"))))); 
123           Node varinit = new StatementEndNode(sv, "", 
124            new BinNode(sv, CMD.SET, "=", 
125             v, 
126             new PushConstNode(sv, "null"))); 
127           Node hasnext = new CallNode(sv, "()", 
128            new BinNode(sv, CMD.DOT, ".", 
129             new VarNode(sv, autoVarName), 
130             new PushConstNode(sv, "hasNext"))); 
131           Node vargennext = new StatementEndNode(sv, "", 
132            new BinNode(sv, CMD.SET, "=", 
133             new VarNode(sv, v.name), 
134             new CallNode(sv, "()", 
135              new BinNode(sv, CMD.DOT, ".", 
136               new VarNode(sv, autoVarName), 
137               new PushConstNode(sv, "next"))))); 
138           return new ListNode(sv, "", 
139            new ListNode(sv, "", 
140             new ListNode(sv, "", 
141              iter 
142             ), 
143             varinit 
144            ), 
145            new WhileNode(sv, "while", 
146             hasnext, 
147             new ListNode(sv, "", 
148              new ListNode(sv, "", 
149               vargennext 
150              ), 
151              s))); 

Sorularınızı cevaplamak için: ne karışıklık göstermek için, ben ne var şimdi sonrası evet, bu kodun utanıyorum.

SORU: Bu bana, bu konuda yani verilen kural şey yapmak var izin ayrıştırıcı jeneratör vardır: başka bir şey sanki onu yeniden yazmak için

FOR LPAREN var_decl COLON expr RPAREN statement 

söyle ayrıştırıcı. Bu iyi bilinen ise

FOR LPAREN var_decl COLON expr RPAREN statement = 
    { with [ x = generateAutoName(); ] 
     emit [ "Iterator $x = makeIterable($expr).iterator();" 
       "while (${x}.hasNext()) {" 
       "$var_decl = ${x}.next();" 
       "$statement" 
       "}" 
     ] 
    } 

bilmiyorum: Ben bu belki benzer (nedeniyle herhangi gramer temelde eksikliği lisp kolaydır) Lisp makro mekanizmasının bir çeşit, gerektirecektir hayal sorun ya da değil, sadece neyi arayacağımı bile bilmiyorum - bulduğum en benzer soru şu: Any software for pattern-matching and -rewriting source code? ama ihtiyaç duyduğum yere yakın değil çünkü ayrı bir adım olarak çalışması gerekiyordu ve derleme sırasında değil, bu yüzden uygun değil.

Herhangi bir yardım için teşekkür ederiz.

Answer 1

Parser'i çok fazla bükmeye çalıştığınızı düşünüyorum. İçinde makro bulunan ağacını oluşturabilir ve daha sonra istediğiniz makroyu değiştirmek istediğinizde makroları değiştirmek için ağacı işlemden geçirebilirsiniz.

Bunu yapmak için, ortaya çıkan ağacı yürüterek, makro düğümlerini (veya yer değiştirmek istediğiniz yerleri) tespit ederek ve basitçe işlem ağacındaki korsanlıkla değiştirerek yapabilirsiniz. Güzel değil ama uygulanabilir. Bunu herhangi bir ayrıştırıcı jeneratörü/AST inşaat makinesi ile yapabilmeniz gerekir.

Daha yapılandırılmış bir yaklaşım istiyorsanız, AST'nizi oluşturabilir ve ardından makroları içeriklerine "yeniden yazmak" için kaynak-kaynak dönüşümlerini kullanabilirsiniz. Out DMS Software Reengineering Toolkit bunu yapabilir, ile ilgili daha fazla bilgiyi transforms look like nolu sayfada bulabilirsiniz.

DMS yaklaşımı kullanarak

, senin konseptin:

term = expr POST_INCR ; 

Tüm bu dilbilgisi kurallarını verecekti:

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)" 

Eğer dilbilgisi kuralı ile geleneksel şekilde orijinal metni ayrıştırmak gerektirir DMS'ye verin ve kaynağını ayrıştırın ve AST'nizi dilbilgisine göre oluşturun.

Sonra Oluşan ağacına bir DMS yeniden yazma geçerlidir: Burada

domain MyToyLanguage; -- tells DMS to use your grammar to process the rule below 

rule replace_POST_INCR(e: expr): term->term 
    = "\e POST_INCR" -> " (tmp = \e; \e = \e + 1; tmp) "; 

alıntı işaretleri "alan meta tırnak" yerine dize alıntılar var. Çift tırnak işaretleri dışındaki metin DMS kural-sözdizimidir. Tırnakların içindeki metin, dilinizden (MyToyLangauge) sözdizimidir ve sağladığınız ayrıştırıcıyı kullanarak ayrıştırılır, \ e gibi desen değişkenleri için bazı özel kaçışlar. (Bu desen ayrıştırma özelliğini elde etmek için dilbilgisine bir şey yapmanız gerekmez; DMS bununla ilgilenir).

DMS ile yapılan sözleşmeyle, genellikle bu tür bir ad kullanmak yerine, lexer'da "++ ++" ile eşdeğer bir karşılığı olan POST_INCR gibi literal tokenleri adlandırabiliriz. Eğer, sonra dilbilgisi kuralı okur bunu yaparsak

#token '++' "\+\+" 

gibi:

term = expr '++' ; 

ve yeniden yazma kuralı şimdi benziyor gibi yerine

#token POST_INCR "\+\+" 

ait lexer kuralı ardından bakar :

rule replace_POST_INCR(e: expr): term->term 
    = "\e++" -> " (tmp = \e; \e = \e + 1; tmp) "; 

Bu kuralı takiben, dilbilgisi (lexer ve BNF) (IMHO) çok daha okunabilir, ve yeniden yazma kuralları daha okunabilirdir, çünkü onlar gerçek dil sözdizimine çok yakındır.

Answer 2

Belki de ANTLR'nin ağaç yeniden yazma kuralları gibi bir şey arıyorsanız. Bazı yardımcı işlevleri tanımlayarak AST yapı sözdizimini daha okunabilir hale getirebilirsiniz. Gözümde, çok fazla artıklık var (neden hem bir numaralandırmaya hem de bir operatör için bir karakter dizisine ihtiyacınız var?) Ama ben bir Java programcısı değilim.

Bir yaklaşım size alabilir:

Başlat zaten AST üretir sizin ayrıştırıcı ile. Şablon argümanlarını ve gensym'leri işlemek için sözcüksel bir sözdizimi veya iki tane ekleyin. Ardından AST'yi yenilemek için AST'yi (Java veya bayt kodu) kodlayan AST yürüteç yazınız. Bunu kullanarak, kendi çözümleyicinizi kullanarak makro şablonları işlevlerini oluşturabilirsiniz; bu, AST'nize yapabileceğiniz değişikliklerle otomatik olarak senkronize kalacağı anlamına gelir.