编译原理学习笔记06_antlr初步

nonoob posted @ Sun, 23 Sep 2012 22:11:10 +0800 in Programming , 4017 readers

antlr是什么

权威解释见官方或wikipedia，我只负责八卦。作者Terence Parr似乎是个有洁癖的人，写了antlr第一个版本之后觉得效率不高又写了v2，因为同样的理由又推倒重来写了v3。尽管以java为主打，但这个antlr非常有野心，Java/C#/Python/Ruby/Scala等语言通吃；由grammar生成lexer和parser使得这玩意儿非常适合教学用，也非常适合菜鸟级程序员提高编写编译器的自信。虽说没有JavaCC这么正统，但是个人觉得非常实用，现在Hibernate framework/Jython/Groovy可都是基于antlr的哦！这哥们还开发了一套template engine，同样是一个妄图大一统文本解析的干活。有了antlr这把锤子他就开始到处乱敲：paper自不用说，然后是《The Definitive ANTLR Reference》、《Language Implementation Patterns》。后者近期被译成中文，号称“屠龙”；虽说的确过誉了，但是不得不承认这本书的确深入浅出。尽管作者一直在自卖自夸antlr和StringTemplate，但是对于java系的人来讲这的确是学习编译原理基础知识的好东西；连Guido大叔和Dalvik设计者Dan Bornstein也对这本书颇有好评。

安装工具

antlr：http://www.antlr.org/download.html

对于我这样的习惯了eclipse的懒人来说antlrworks并不是上上之策，插件才是王道http://antlrv3ide.sourceforge.net/。

该插件特点：

新建一般的java project（如果要生成的目标语言是java的话）并convert成antlr即可，之后只需写grammar文件。
默认情况下保存每一次grammar文件就会进行自动生成对应的lexer和parser的java文件（默认target language是java）和对应tokens文件；每次打开eclipse时会重新解析一次。
似乎生成的lexer和parser并不会添加grammar文件所在package信息（吐槽：这一点和上面一个特点加起来足以让人抓狂！！！）。
编辑器的content assit功能和java编辑器的功能有不少出入，括号、引号、缩进等功能做得并不好。
grammar（g文件）除编辑器的两个tab Interpreter和Railroad view非常棒，一个用于傻瓜式写，一个用于GUI显示，并且可以导出成html。

还可以考虑使用StringTemplate：http://www.stringtemplate.org/download.html

开始使用

以含有加减乘法的计算器且目标语言java为例。

在g文件中写出所要定义的grammer（一般是词法和语法的综合）

grammar Expr;

prog : stat+;
stat : expr NEWLINE
     | ID '=' expr NEWLINE
     | NEWLINE
     ;
expr: multiExpr (('+'|'-') multiExpr)*
    ;  
multiExpr : atom('*' atom)*
    ;   
atom : INT
     | ID
     | '(' expr ')'
     ;
     
ID : ('a'..'z'|'A'..'Z')+ ;
INT : '0'..'9'+;
NEWLINE : '\r'?'\n';
WS : (' '|'\t'|'\n'|'\r')+{skip();};

生成的ExprLexer.java文件中会将'(',')'等涉及判定的字符用新的identifier如T__8等来对应，识别这样的字符的方法形如T__8。新生成的ExprLexer类继承了antlr定义的Lexer类，封装了一些方法。ExprParser继承Parser类，诸如expr等g文件中的左式会有个对应的方法（例如expr()）来处理它；为了处理出错和从错误状态恢复，该类还生成了FOLLOW_expr_in_stat34这样的变量并调用了pushFollow()这类方法。
这样，从输入流中可以生成lexer对象，将由lexer得到的tokens作为输入就得到一个parser对象；调用顶层的方法就可以完成语法分析了。

public static void main(String[] args) throws IOException, RecognitionException {
		// TODO Auto-generated method stub
		ANTLRInputStream input = new ANTLRInputStream(System.in);
		ExprLexer lexer =  new ExprLexer(input);
		CommonTokenStream tokens = new CommonTokenStream(lexer);
		ExprParser parser = new ExprParser(tokens);
		parser.prog();
	}

上述代码对于符合grammar的输入不会有输出，如果需要给出相应的输出的话仍可以在g文件中添加（java）代码。

添加包含的package

@header{
import java.util.HashMap;
}

添加parser中的成员变量

@members{
/** Map variable name to Integer object holding value */
HashMap memory = new HashMap();
}

添加parser中左式处理函数的返回值（前面代码中的方法的返回值都为void），并且在每个生成式上在{}里添加特定的方法。值得注意的是对于诸如INT这样在lexer中得到的Token用的是antlr定义好的Token类的一个对象，包含了getText()方法；故不需要定义INT的text返回值。如下面的一段：

expr returns [int value]
     : e=multExpr {$value = $e.value;}
     ( '+' e=multExpr {$value+=$e.value;}
     | '-' e=multExpr {$value-=$e.value;}
     )*
    ;

multExpr returns [int value]
     : e = atom {$value=$e.value;}('*' e=atom {$value *= $e.value;})*

atom returns [int value]
    :   // value of an INT is the int computed from char sequence
     INT {$value=Integer.parseInt($INT.text);}
     | ID	// variable reference
     {
        // look up value of variable
        Integer v = (Integer)memory.get($ID.text);
        // if found, set return value else error
        if(v!=null) $value = v.intValue();
        else System.err.println("undefined variable "+$ID.text);
     }
        // value of parenthesized expression is just the expr value
     | '(' expr ')'{$value=$expr.value;}
     ;

--------------------------------------------------

参考自《The Definitive ANTLR Reference》，又是一本没付版权费的电子书:(

PS：通过antlr生成的代码，我才知道java对于退出多重循环有个不错的做法，就是在指定的循环前面添加上某个label，然后在要退出的时候加上break label。我们都知道尽管java把goto作为保留字，但是在咱码农是没法用goto的。使用这样break的做法肯定没有C/C++来得凶残；但是无疑很好地避免了goto带来的无结构编程恶习，同时又保留了灵活性（似乎该对D.E.Knuth致敬？）。

Comments (32)

[Reply]

middleware said:
Wed, 26 Sep 2012 09:33:05 +0800

ANTLR 确实不错。LL'(k) basically makes LALR obsolete. 而且还支持回溯 parsing（通过 exception），基本解决了左递归和不确定语法的问题。这是我 04 年看的时候的成果。

[Reply]

meidir said:
Thu, 21 Jul 2022 20:48:14 +0800

Glad to be one of the visitors on this awe inspiring web site. Aputure

[Reply]

meidir said:
Wed, 24 Aug 2022 19:22:39 +0800

Some times its a pain in the ass to read what blog owners wrote but this website is really user pleasant! . skin

[Reply]

meidir said:
Wed, 24 Aug 2022 23:33:05 +0800

Wow, Exactly what a Excellent post. I really found this to much informatics. It is what i was searching for.I wish to suggest you that please keep sharing such form of info.Thanks opbest

[Reply]

Linker SEO said:
Wed, 03 Jan 2024 01:37:24 +0800

The industry needs to focus on creating more robust slots. เว็บตรง แตกง่าย

[Reply]

Linker SEO said:
Thu, 04 Jan 2024 14:22:05 +0800

I'm hooked! The biggest web slots here are a true spectacle. สล็อตเว็บใหญ่ที่สุด

[Reply]

Linker SEO said:
Mon, 15 Jan 2024 14:16:49 +0800

I for one utilize them solely astounding components : you will see these people amid: รวมสล็อตทุกค่ายในเว็บเดียว

[Reply]

jsimitseo said:
Tue, 16 Jan 2024 18:04:42 +0800

You bear through a wonderful opening. I rational soundness unquestionably quarry it besides by and by propose to my buddys. I am reserved they assurance be profited from this scene. เกมส์ไพ่ป๊อกเด้ง

[Reply]

jsimitseo said:
Wed, 17 Jan 2024 01:21:19 +0800

Trying to say thanks won't simply be adequate, for the fantasti c clarity in your written work. I will quickly get your rss channel to remain educated of any updates. เว็บสล็อตโรม่า

[Reply]

jsimitseo said:
Fri, 02 Feb 2024 22:18:55 +0800

I likewise composed an article on a comparative subject will discover it at compose what you think. concierge doctor

[Reply]

Matthew Wade said:
Sun, 08 Dec 2024 00:32:35 +0800

As I website possessor I think the content material here is really superb , appreciate it for your efforts. ECサイトセキュリティ

[Reply]

Matthew Wade said:
Sun, 08 Dec 2024 00:33:00 +0800

Deference to website author , some great entropy. EC-CUBE カスタマイズ

[Reply]

Matthew Wade said:
Fri, 13 Dec 2024 17:04:21 +0800

I love blogging and i can say that you also love blogging . 大人動画

[Reply]

Matthew Wade said:
Sun, 15 Dec 2024 19:37:19 +0800

I like what you guys are up also. Such intelligent work and reporting! Carry on the excellent works guys I have incorporated you guys to my blogroll. I think it’ll improve the value of my web site 【フル映像】

[Reply]

Matthew Wade said:
Tue, 17 Dec 2024 21:05:27 +0800

The article posted was very informative and useful. You people are doing a great job. Keep going. 盗撮エロ動画

[Reply]

Matthew Wade said:
Tue, 17 Dec 2024 21:05:55 +0800

Respect to website author , some good selective information . エロ動画のフル動画

[Reply]

Matthew Wade said:
Sat, 21 Dec 2024 20:04:49 +0800

Thanks for this post, I am a big fan of this website would like to go on updated. Japanese Pokemon Card

[Reply]

Matthew Wade said:
Fri, 07 Aug 2026 23:30:28 +0800

西宮市で家族葬や一日葬を検討する方に向けて、それぞれの特徴や費用の考え方、葬儀社を選ぶときに確認しておきたいポイントを紹介します。西宮市　葬儀社

西宮市で葬儀社を探す際に役立つ情報を紹介。葬儀プランの種類や費用、見積もりで確認したい項目など、安心して依頼するためのポイントを解説します。西宮市　葬儀社

西宮市で葬儀社を比較するときのポイントを紹介します。料金だけでなく、葬儀プランやスタッフの対応、アフターサポートなどを確認して選びましょう。西宮市　葬儀社

西宮市で費用を抑えながら葬儀を行いたい方へ。家族葬や一日葬などのプランを選ぶ際のポイントや、見積もりで確認すべき費用を解説します。西宮市　葬儀社

[Reply]

Matthew Wade said:
Thu, 13 Aug 2026 21:06:52 +0800

本編フル動画を楽しみたい方に向けて、視聴方法や注目ポイントをわかりやすく紹介します。本編フル

本編フルを探している方へ、作品をより楽しむための視聴ポイントやチェックしたい情報を紹介します。本編フル

AVメーカー【SODクリエイト】の作品情報を専門にまとめたサイト。人気作品や注目作品などを分かりやすく紹介します。 AVメーカー【SODクリエイト】作品専門まとめサイト

本編フル動画の魅力や見どころを知りたい方に向けて、視聴前にチェックしたいポイントをわかりやすく解説します。本編フル

本編フルの内容を楽しみたい方必見。作品の見どころや視聴時に注目したいポイントを詳しく紹介します。本編フル

[Reply]

Matthew Wade said:
Sat, 15 Aug 2026 20:39:04 +0800

I am curious to find out what blog platform you have been utilizing? I’m having some minor security problems with my latest website and I would like to find something more risk-free. Do you have any solutions? あくめくん

[Reply]

Matthew Wade said:
Thu, 20 Aug 2026 19:25:16 +0800

既婚者マッチングの特徴や利用方法を紹介。既婚者同士だからこそ理解しやすい悩みや価値観を共有できる出会いを探しましょう。既婚者マッチング

【無料エロ漫画】を探している方に向けて、話題の作品や読みやすいマンガ情報を紹介。作品の特徴や魅力をチェックして、お気に入りの一作を見つけよう。【無料エロ漫画】

【フル漫画無料!!】で楽しめる話題の漫画や作品の魅力を紹介。無料で漫画を読む際のポイントやおすすめの楽しみ方を詳しく解説します。【フル漫画無料!!】

【最新フル漫画free】で話題の漫画作品を探す方へ、作品情報や読み方をわかりやすく紹介。気になる漫画をチェックできます。【最新フル漫画free】

素人エロ動画に関する話題や作品の特徴を紹介。人気の傾向や楽しみ方をチェックして、自分に合ったコンテンツを探せます。素人エロ動画

同人エロ漫画の作品情報やジャンル、魅力などを紹介。さまざまな同人作品の特徴をチェックしながら、自分に合った作品を探せるガイドです。同人エロ漫画

素人無料動画に関する情報をわかりやすく紹介。注目されている動画の特徴や楽しみ方、関連コンテンツをチェックして、自分に合った動画を探せます。素人無料動画

同人エロマンガの特徴や魅力、作品の探し方を紹介。多彩なジャンルから自分に合った作品を見つけるためのポイントを詳しく解説します。同人エロマンガ

素人エロ動画に関する話題や作品の特徴を紹介。さまざまなジャンルの魅力をわかりやすくチェックできます。素人エロ動画

素人エロ動画Loverに関する情報を紹介。話題の動画や作品の特徴をチェックしながら、気になるコンテンツを探せます。素人エロ動画Lover

エロ動画城【素人館】で楽しめる素人エロ動画を紹介。話題の作品や人気コンテンツをチェックして、お気に入りを探せます。エロ動画城【素人館】

シコレビューで話題の動画や出演女優について紹介。気になる作品情報や女優名をチェックして、気になる動画を見つけよう。シコレビュー【あのエロ動画に出演する女優名は何？】

エロ動画まとめ「3150！（サイコー）」の人気コンテンツを紹介。話題の動画や注目作品をチェックして、お気に入りを探せます。エロ動画まとめ「3150！（サイコー）」

【無料立読みフル漫画】で話題の作品をチェック。無料で読める漫画の魅力や作品情報をわかりやすく紹介します。【無料立読みフル漫画】

[Reply]

Matthew Wade said:
Sun, 23 Aug 2026 16:18:05 +0800

新人・デビュー作品を中心に、話題のAV動画をまとめて紹介。新人女優のプロフィールや作品情報などをチェックできます。新人・デビュー専門！AV動画まとめサイト

--------------------------------------------------------------------------------------------

熟女専門のAV動画まとめサイト。大人の魅力を楽しめる作品を厳選して紹介し、気になる動画を見つけやすくまとめています。熟女専門！AV動画まとめサイト

[Reply]

Matthew Wade said:
Sun, 06 Sep 2026 19:37:50 +0800

【本編フル】で話題の動画をチェック。気になる内容や注目シーン、見どころをわかりやすく紹介します。【本編フル】

Comic Loungeは、同人マンガの作品情報を探せるサイトです。気になる作品や作家をチェックして、あなた好みのマンガを見つけよう。 Comic Lounge

【本編フル】の動画内容を詳しく紹介。注目ポイントや見どころをチェックして、話題の動画を楽しみましょう。【本編フル】

同人漫画の魅力やジャンル、作品の楽しみ方について詳しく紹介。自分に合った作品を見つけるためのポイントも解説します。同人漫画

【本編フル】で注目されている動画の内容や見どころを紹介。話題のポイントをわかりやすくまとめています。【本編フル】

[Reply]

Matthew Wade said:
Thu, 10 Sep 2026 20:21:52 +0800

新作＆デビュー作品の最新情報をまとめて紹介。注目の作品や出演者情報をチェックしながら、気になる作品を見つけよう。新作＆デビューAVまとめ

おすすめエロ動画をまとめて紹介。人気ジャンルや話題の作品を探している方に向けて、見つけやすく整理しています。おすすめエロ動画まとめ

素人エロ動画GIFを探している方に向けて、話題のGIF動画や関連コンテンツをまとめて紹介します。素人エロ動画GIF

最新の素人動画に関する情報を紹介。話題のコンテンツや注目ポイントをチェックして、自分に合った動画を探そう。最新の素人エロ動画

FANZA独占動画をまとめて紹介。注目の独占作品を探しやすく整理し、気になる動画をチェックできます。 FANZA独占動画まとめ

ニューシロウト！に登場する素人動画の女優名が気になる方へ。出演者情報や作品の特徴、確認方法などをわかりやすく紹介します。ニューシロウト！あの素人動画の女優名は？

最新VR動画をまとめて紹介。話題のVR作品や注目コンテンツをチェックしながら、気になる動画を見つけられます。最新VR動画まとめ

人気エロ同人マンガの特徴や作品選びのポイントを紹介。ジャンルや作風の違いを比較し、自分に合う作品を探すための情報をまとめます。人気エロ同人マンガ

人気VR研究所では、VRの最新情報や話題のコンテンツ、注目作品などを詳しく紹介。VRの魅力をわかりやすく解説します。人気VR研究所

エロ漫画の特徴や魅力、作品を楽しむためのポイントをわかりやすく紹介。ジャンルや表現の違いにも触れながら解説します。エロ漫画

ゴールデンバズーカについて詳しく解説。基本情報や特徴、魅力、楽しみ方などをわかりやすく紹介します。ゴールデンバズーカ

[Reply]

Matthew Wade said:
Fri, 11 Sep 2026 19:09:32 +0800

エロ同人誌の特徴やジャンル、作品を楽しむ際のポイントについて詳しく紹介。自分に合った作品を見つけるための基礎知識を解説します。エロ同人誌

[Reply]

Matthew Wade said:
Fri, 18 Sep 2026 16:27:10 +0800

エロフルでエロい動画をフルで楽しみたい方へ。さまざまな動画コンテンツを見つけやすくまとめ、気になる作品をチェックできます。エロフル！エロい動画をフルでお届けします！

raw漫画保管庫について、漫画RAWの保存や閲覧に関する基本情報をわかりやすく解説。利用時に知っておきたいポイントも紹介します。 raw漫画保管庫

[Reply]

Matthew Wade said:
Mon, 28 Sep 2026 03:31:20 +0800

女優コードについて、基本的な意味や検索時に知っておきたい情報をわかりやすく解説。関連するコード情報の見方も紹介します。女優コード

エロ同人サーチについて、同人作品を探す際の検索方法や基本的な使い方をわかりやすく解説。作品検索のポイントも紹介します。エロ同人サーチ

[Reply]

Matthew Wade said:
Wed, 30 Sep 2026 16:17:02 +0800

既婚者マッチングアプリの特徴や基本的な使い方を解説。サービスを比較するときのポイントや利用前に確認したい点も紹介します。既婚者マッチングアプリ

[Reply]

Matthew Wade said:
Mon, 05 Oct 2026 03:35:35 +0800

「エロ動画」に関する基本情報を紹介。動画を探す際に知っておきたい安全性やプライバシー、年齢確認などのポイントをわかりやすく解説します。「エロ動画」

[Reply]

Matthew Wade said:
Mon, 05 Oct 2026 03:35:46 +0800

「エロ動画」を利用する際に確認したい安全対策やプライバシー保護、年齢確認などの基本ポイントをわかりやすく紹介します。「エロ動画」

[Reply]

Matthew Wade said:
Mon, 05 Oct 2026 03:35:56 +0800

「エロ動画」を探すときに役立つ基本情報を紹介。安全性や個人情報、サイト利用時に確認したいポイントを詳しく解説します。「エロ動画」

[Reply]

Matthew Wade said:
Mon, 12 Oct 2026 16:46:56 +0800

raw漫画保管庫に関する情報をわかりやすく紹介。漫画RAWの特徴や閲覧時の注意点、安全に漫画を楽しむためのポイントを解説します。 raw漫画保管庫

随便写写

Computers are like bikinis. They save people a lot of guesswork. --Sam Ewing

编译原理学习笔记06_antlr初步