index.html

<!doctype html>
<html lang="en">

	<head>
		<meta charset="utf-8">

		<title>ANTLR - Parser Generator</title>

		<meta name="apple-mobile-web-app-capable" content="yes" />
		<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />

		<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">

		<link rel="stylesheet" href="css/reveal.min.css">
		<link rel="stylesheet" href="css/theme/haefele.css" id="theme">

		<!-- For syntax highlighting -->
		<link rel="stylesheet" href="lib/css/zenburn.css">

		<!-- If the query includes 'print-pdf', use the PDF print sheet -->
		<script>
			document.write( '<link rel="stylesheet" href="css/print/' + ( window.location.search.match( /print-pdf/gi ) ? 'pdf' : 'paper' ) + '.css" type="text/css" media="print">' );
		</script>
		
		<style type="text/css">


		.reveal .controls {
		    bottom: 15%;
		    z-index: 1;
		}

		.reveal section img {
			width: 100%;
			height: 100%
		}

		div.headR {
			    top: 1%;
			    display: block;
			    position: absolute;
			    right: 1%;
			    z-index: 1;
			    width: 15%;
			    height: 15%;
			    direction: rtl;
		}
		div.headL {
			    top: 1%;
			    display: block;
			    position: absolute;
			    left: 1%;
			    z-index: 1;
			    width: 15%;
			    height: 15%;
		}
		div.footL {
			    bottom: 1%;
			    display: block;
			    position: absolute;
			    left: 1%;
			    z-index: 30;
			    width: 15%;
			    height: 15%;
			    text-align: left;
		}
		div.footR {
			    bottom: 1%;
			    display: block;
			    position: absolute;
			    right: 1%;
			    z-index: 30;
			    width: 15%;
			    height: 15%;
			    direction: rtl;
		}
		
		div.headC {
			    top: 1%;
			    display: block;
			    position: absolute;
			    left: 40%;
			    z-index: 30;
			    width: 20%;
			    height: 10%;
	    		text-align: center;
		}
		
		div.footC {
			    bottom: 1%;
			    display: block;
			    position: absolute;
			    left: 40%;
			    z-index: 30;
			    width: 20%;
			    height: 10%;
	    		text-align: center;
		}
		
		footnote {    
			display: inline-block;
    		font-size: 0.6em;
	    	line-height: 1.2em;
		    vertical-align: text-bottom;
		    position: absolute; bottom: 0;
		}
		
		div.slide-chapter {
			display: inline-block;
    		font-size: 0.7em;
    		font-weight: bold;
	    	line-height: 1.2em;
		    vertical-align: top;
		    position: absolute; top: 0;
		    width: 100%;
		    left: 0;
		}
		
		div.slide-title {
			display: inline-block;
    		font-size: 0.7em;
    		font-weight: bold;
	    	line-height: 1.2em;
		    vertical-align: bottom;
		    position: absolute; bottom: 0;
		    width: 100%;
		    left: 0;
		}
		
		.titlePage {
			text-align: center;
		}
		
		</style>

		<!--[if lt IE 9]>
		<script src="lib/js/html5shiv.js"></script>
		<![endif]-->
	</head>

	<body>

		<div class="reveal">

<div class="staticElements">
	<div class="headR">
	<img src="img/dh-Logo.png"></img>
	</div>
	<div class="headL">
	<!--<img src="img/rheadLogo.png"></img>-->
	</div>
	
	
	<div class="headC"><div class="slide-chapter">test</div></div>
	<div class="footC"><div class="slide-title">test</div></div>
	
	<div class="footL">
	<footnote>Andreas Stadelmeier</footnote>
	</div>
	<div class="footR">
	<footnote>Folie <text class="slide-number"></text></footnote>
	</div>
</div>
			<!-- Any section element inside of this container is displayed as a slide -->
			<div class="slides">



<!-- Titelblatt -->
<section data-markdown data-separator="!---" data-vertical="u---" class="titlePage">
<script type="text/template">
# ANTLR - Parser Generator #

-----

### <b>A</b>nother <b>T</b>ool for <b>L</b>anguage <b>R</b>ecognition ###

#### Vorlesung und Übungen zum praktischen Umgang mit dem ANTLR Parser Generator ####

-----

<footnote>Andreas Stadelmeier</footnote>
</script>
</section>


<section data-markdown data-separator="!---" data-vertical="u---">
<script type="text/template">

## Organisatorisches ##
* Ablauf der Volesung gliedert sich in 3 Teile:
    1. Vorlesung
    2. Übungsblatt (in 2er Gruppen bearbeiten)
    3. Vorstellen/Besprechen der Ergebnisse
* Bearbeiten der Aufgaben mit eigenem Laptop (Jede Zweiergruppe sollte einen Rechner besitzen)

!---

## Literatur ##
* [Offizielle ANTLR-Website: antlr.org](http://antlr.org)
* "The Definitive ANTLR 4 Reference" von Terence Parr, ISBN: 978-1-93435-699-9
* "Drachenbuch"

u---

### Dokumenation und Hilfe im Internet ###
* [Dokumentation auf antlr.org](https://theantlrguy.atlassian.net/wiki/display/ANTLR4/ANTLR+4+Documentation)
* [Stackoverflow ANTLR-Tag](https://stackoverflow.com/questions/tagged/antlr)
* [ANTLR - Google Group](https://groups.google.com/forum/#!forum/antlr-discussion)


!---

## Parser Generator ##
* Ein Parser Generator erzeugt einen Parser aus einer Formalen Beschreibung einer Sprache

* ANTLR v4:
	* Formale Beschreibung: G4-Grammatik
	* Erzeugter Parser: Java-Klassen

u---

### Vorzüge von ANTLR ###
* Trennung von Grammatik und Verarbeitungslogik
	* Programm verarbeitet den geparsten Syntaxbaum. Kein Java-Source Code innerhalb der Grammatik
	* Bessere Integration des SourceCodes in die IDE
	* Leichter anpassbar/erweiterbar
	* Arbeiten mit bekannter Java Syntax

* Eigene Entwicklungsumgebung für ANTLR Grammatiken (ANTLRWorks), sowie Plugins für gängige Java IDEs, wie Eclipse und Intellij IDEA
	* Syntax Highlighting
	* Code Completition

* Gute Dokumentation
* Gute Fehlerausgabe

!---

## G4-Grammatik ##

## Syntax ##
* Comments sind gleich wie in Java (/**/ //)
* Tokens/Terminale beginnen mit Großbuchstaben, Non-Terminale mit Kleinbuchstaben
* Literale in Single-Quotes ('literal')
* Regeln bestehen aus Namen für Token, Literale und den Zeichen ( | , * , + , ? ) 
	* | entspricht "Oder"
	* *, + , ? , . verhalten sich wie bei Regulären Ausdrücken
	* ~[A] entspricht allen 16-bit wertigen Zeichen außer 'A'

u---

### Syntax Veranschaulichung ###

	//Name der Grammatik. Muss mit dem Dateinamen übereinstimmen
	grammar GrammatikBeispiel; 
	regel1 : Token1 Token2;
	Token1 : 'Hallo';
	Token2 : [a-z]+;
	/*
	Grammatik parst Texte der Form:

	Hallo nameinkleinbuchstaben
	*/
	Linefeed: '\r'? '\n'; //'\r' für Windows linefeed
	WS : [ \t]+ -> skip; //Überspringen aller Leerzeichen

u---

### G4-Grammatik Beispiel ###

	grammar Beispiel2;
	s : s '(' s ')' s
	  | TEXT?;
	TEXT : ~[()]+;

Gibt es ein äquivalent zu dieser Grammatik als regulären Ausdruck?

u---

## Hinweise ##
* Keine separate Datei für Lexeme notwendig. Alle Regeln und Lexeme werden in der G4-Grammatik beschrieben.
* Der Lexer nimmt immer das erste in der Grammatik auftauchende Lexem. Allgemeinere Terminale also ans Ende der Grammatik verlegen.


	//Warum kann diese Grammatik "int 1" nicht parsen?
	grammar Number;
	number : integer | float;
	integer : 'int ' Integer;
	float : 'float ' Float;

	Float : [0-9\.];
	Integer : [0-9];

* Bei nicht eindeutigen Regeln wird die zuerst spezifizierte Regel bevorzugt
* ANTLR Fehlermeldungen und Warnungen beachten

u---

	expr : expr '+' expr | expr '*' expr | Number;


Baum beim Parsen von "1 &#42; 2 + 2 &#42; 3"


![BaumFalsch][1]

  [1]: img/baumFalsch.jpg
	
	//Bevorzugt Punkt vor Strich:
	expr : expr '*' expr | expr '+' expr | Number;

u---

	//Bevorzugt Punkt vor Strich:
	expr : expr '*' expr | expr '+' expr | Number;


Baum beim Parsen von "1 &#42; 2 + 2 &#42; 3"


![BaumRichtig][1]

  [1]: img/baumRichtig.jpg
	


!---

## Entwicklungsumgebung ##
[Übersicht:](http://tunnelvisionlabs.com/products/demo/antlrworks)

* [ANTLR als JAR-Datei](https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Getting+Started+with+ANTLR+v4) lässt sich zusammen mit jeder Entwicklungsumgebung auf jedem gängigen Betriebssystem nutzen.
* ANTLR lässt sich per Plugin in gängige Java IDEs integrieren:
	* [IntelliJ-Plugin](http://plugins.jetbrains.com/plugin/7358?pr=idea)
	* [Eclipse-Plugin](https://github.com/jknack/antlr4ide)
* [ANTLR Works IDE](http://tunnelvisionlabs.com/products/demo/antlrworks)(Netbeans)

!---

## Übngsblock 1 ##

### Übungsblatt 1: Aufgabe 1 und 2 ###
[Link zum Übungsblatt: www2.ba-horb.de/~stan/übung1.pdf](http://www2.ba-horb.de/~stan/%C3%BCbung1.pdf)

[Intellij-Download](https://www.jetbrains.com/idea/download)

[Download der ANTLR-Java-Library](http://www.antlr.org/download/antlr-4.4-complete.jar)

#### Installation des ANTLR Plugins in Intellij:
* File -> Settings -> Suche nach "Antlr v4 Grammar Plugin"
* oder: [Download ANTLR-Plugin für Intellij](https://plugins.jetbrains.com/plugin/download?pr=idea&updateId=26416)



!---

## Parse Tree Walker ##
* Der generierte Parser liest den ihm übergebenen Text zu einem Syntaxbaum ein
* Dieser kann anschließend mittels der von ANTLR angebotenen API durchlaufen werden.
* Der Syntaxbaum wird dabei mittels einer Tiefensuche durchlaufen
* Zu jeder Regel in der Grammatik kann eine Methode spezifiziert werden, welche beim durchlaufen des zugehörigen Knotens im Syntaxbaum aufgerufen wird

u---

### Implementierung ###
* Der Parser generiert einen Parse Tree aus dem eingelesenen Text
* Dieser kann anschließend mittels eines ParseTreeListeners durchlaufen werden
* Zur Implementierung eines ParseTreeListener sollte die Klasse BaseListener erweitert werden
	* Diese Klasse verfügt über alle Methoden, welche beim Durchlaufen des Syntaxbaums aufgerufen werden.
	* Um gewisse Knoten zu verarbeiten müssen diese Methoden überschrieben werden:


	@Override
    public void enter<NameDerRegel>(@NotNull MarkdownParser.DocumentContext ctx) {
    	//...
    }


u---

### Implementierung ###
* Eine Instanz dieses Listeners kann anschließend einem ParseTreeWalker übergeben werden. Dieser durchläuft den Syntaxbaum und ruft die entsprechenden Methoden im Listener auf.
* Beispiel für das Aufrufen eines ParseTreeWalkers für eine Grammatik namens 'Beispiel':


	// Der Text wird über den Standard-Input eingelesen:
	ANTLRInputStream input = new ANTLRInputStream(System.in);
	// Text parsen:
	BeispielLexer lexer = new ArrayInitLexer(input);
	CommonTokenStream tokens = new CommonTokenStream(lexer);
	BeispielParser parser = new ArrayInitParser(tokens);
	ParseTree tree = parser.init(); // Das Parsen mit der Regel init beginnen
	// ParseTreeWalker generieren, welcher die Methoden im Listener aufruft:
	ParseTreeWalker walker = new ParseTreeWalker();
	// Listener erstellen:
	SelbstgeschriebenerListener listener = new SelbstgeschriebenerListener();
	// Den Syntaxbaum durchlaufen:
	walker.walk(listener, tree); 


!---

## Übngsblock 2 ##

### Übungsblatt 1: Aufgabe 3 ###

u---

## Beispielimplementierungen für Aufgabe 3.b ##
### Grammatik für Expressions (Fehlerhaft) ###

	grammar IntExpression;
	s : expr;

	expr : expr ADD expr | expr MUL expr | expr ADD expr | '(' expr ')'
	     | Number;

	MUL : '*' ;
	ADD : '+' ;
	SUB : '-' ;

	Number : [0-9]+;
	WS : [ \t\r\n] -> skip;


u---

### Methode zum Einlesen und Parsen eines Strings aus System.in ###


    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        ExpressionBeispielLexer lexer = new ExpressionBeispielLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ExpressionBeispielParser parser = new ExpressionBeispielParser(tokens);
        ParserRuleContext tree = parser.s(); //Parsen

        ParseTreeWalker walker = new ParseTreeWalker(); // create standard walker
        ExpressionCalculator extractor = new ExpressionCalculator();
        walker.walk(extractor, tree); // initiate walk of tree with listener
    }


u---

### ParseTreeListener ###

	public class ExprEvaluator extends IntExpressionBaseListener{
	    @Override
	    public void exitS(IntExpressionParser.SContext ctx) {
	        int result = new ExprAdapter().adapt(ctx.expr());
	        System.out.println(result);
	    }
	}


### ExprAdapter ###

	class ExprAdapter{
	    int adapt(IntExpressionParser.ExprContext ctx){
	        if(ctx.MUL()!=null){
	            return this.adapt(ctx.expr(0)) * this.adapt(ctx.expr(1));
	        }else
	        if(ctx.ADD()!=null){
	            return this.adapt(ctx.expr(0)) + this.adapt(ctx.expr(1));
	        }else
	        if(ctx.Number()!=null){
	            return Integer.parseInt(ctx.Number().toString());
	        }
	        return 0;
	    }
	}


!---

## Markdown Parser ##
[Markdown-Syntax](http://daringfireball.net/projects/markdown/syntax)
[Markdown-Editor: stackedit.io](https://stackedit.io/)

!---

## Adapter ##
* Verarbeiten des ParseTrees mittels Adaptern
* Für jedes Kontextobjekt im ParseTree wird ein zugehöriger Adapter implementiert
* Jeder Adapter verarbeitet immer nur die Informationen in seinem Kontext
* Tauchen in seinem Kontext Regeln auf, kann er diese von den zuständigen Adaptern verarbeiten lassen

!---

## Error Listener ##
* Beim Parsen eines fehlerhaften Inputs, gibt der von ANTLR generierte Parser Fehlermeldungen im Standard-Output aus
* Diese Fehler können abgefangen und durch eine eigene Fehlerausgabe verarbeitet werden

u---

### Implementierung eines ErrorListeners ###


	public static class VerboseListener extends BaseErrorListener {
		@Override
		public void syntaxError(Recognizer<?, ?> recognizer,
			Object offendingSymbol,
			int line, int charPositionInLine,
			String msg,
			RecognitionException e)
		{
			// Verarbeitungslogik
		}
	}


u---

### Anfügen des ErrorListeners ###


	SimpleParser parser = new SimpleParser(tokens); //Parser erstellen
	parser.removeErrorListeners(); // Standard ErrorListener entfernen
	parser.addErrorListener(new VerboseListener()); // eigenen Listener anfügen
	parser.prog(); // parsen...


</script>
</section>


<!--
### Rule Context Object ###
* Parser erstellt für jede Regel eine Context-Klasse
* Enthält alle in dieser 

<section data-markdown data-separator="!---" data-vertical="u---">
<script type="text/template">
## Image ##
![Testimage][1]

  [1]: img/test.gif

</script>
</section>
-->
				
			</div>

		</div>

		<script src="lib/js/head.min.js"></script>
		<script src="js/reveal.min.js"></script>
		<script src="js/jquery-2.0.2.min.js"></script>
		
		<script>
		$(".staticElements").hide();
		
		Reveal.addEventListener( 'ready', function( event ) {
		    // event.currentSlide, event.indexh, event.indexv
			$(".slide-title").html($("h1").html()); // set the slide title Divs to the first h1 in the presentation
		} );

		// Fires each time a new slide is activated
		Reveal.addEventListener( 'slidechanged', function( event ) {
			$(".slide-title").html($("h1").html());
		    // event.previousSlide, event.currentSlide, event.indexh, event.indexv
		    if(event.indexh>0){
		    	var slideNumber = "";
		    	$(".staticElements").show();
		    	slideNumber += event.indexh;
		    	if(event.indexv > 0)slideNumber += "."+event.indexv;
		    	$(".slide-number").html(slideNumber);
		    }else{
		    	$(".staticElements").hide();
		    }
			if(event.indexv!=0){
			    for(var headingNumber = 1; headingNumber < 7 ; headingNumber++){
				    var currentChapter = $(Reveal.getSlide(event.indexh,0)).find("h"+headingNumber);
				    if(currentChapter.length > 0){
				    	$(".slide-chapter").html($(currentChapter[0]).html());
				    	return;
				    }
			    }
			}
			$(".slide-chapter").html("");
			} );
		
			// Full list of configuration options available here:
			// https://github.com/hakimel/reveal.js#configuration
			Reveal.initialize({
				controls: true,
				progress: true,
				history: true,
				center: true,

				width: 1300,
			    height: 900,
			    margin: 0.15,
			    
				theme: Reveal.getQueryHash().theme, // available themes are in /css/theme
				transition: Reveal.getQueryHash().transition || 'default', // default/cube/page/concave/zoom/linear/fade/none

				// Optional libraries used to extend on reveal.js
				dependencies: [
					{ src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
					{ src: 'plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
					{ src: 'plugin/zoom-js/zoom.js', async: true, condition: function() { return !!document.body.classList; } },
					{ src: 'plugin/notes/notes.js', async: true, condition: function() { return !!document.body.classList; } }
					// { src: 'plugin/search/search.js', async: true, condition: function() { return !!document.body.classList; } }
					// { src: 'plugin/remotes/remotes.js', async: true, condition: function() { return !!document.body.classList; } }
				]
			});
			
			
		</script>

	</body>
</html>