{
	"0: data": {
		"srcIndexStart": "0", 
		"file": "docssrc/docs.Start.LearnParsing.tmpl", 
		"parseTreeMode": "true", 
		"srcLength": "11869", 
		"source": "[$name|LearnParsing$]
[$title|Never Used a Parsing Tool?$]
[$frame|HTMLPage.tmpl$]

<ul>
<li>[$pageLink|#Compilers|   How a Compiler Works $]</li>
<li>[$pageLink|#Frontend|    The Frontend: Lexing, Parsing, AST and Semantics $]</li>
<li>[$pageLink|#ParsingTool| Using a Parsing Tool $]</li>
<li>[$pageLink|#Next|        The Next Step        $]</li>
<li>[$pageLink|#More|        More Information     $]</li>
</ul>

<a name=\"Compilers\" />
<h3 style=\"margin-bottom: 0px;\">How a Compiler Works</h3>
<h4 style=\"margin-top: 0px;\">(Or: How can I use Goldie to create a compiler?)</h4>
<p>
There's a common misconception that language tools and computer science
theory have advanced enough that creating a compiler can be fully-automated.
This is not true. Only <em>certain parts</em> of writing a compiler can be
automated, and it's only these parts that parsing tools (such as Goldie, GOLD,
Lex/YACC, Flex/Bison and ANTLR) automate. A fully-working compiler is a
complex program that contains many different parts.
</p>
<p>
Here is a diagram of the three main parts of a compiler:
</p>
<div style=\"text-align: center;\">
	<img alt=\"Compiler Diagram\" src=\"[$urlToRoot$]compiler-components.png\" />
</div>
<ol>
<li>
<p>
<span style=\"font-weight: bold\">Frontend:</span>
This is the only part of a compiler that automated parsing tools deal with.
Even so, automated parsing tools only deal with <em>part</em> of the frontend
(see the section
[$pageLink|#Frontend|The Frontend: Lexing, Parsing, AST and Semantics$]
below).
</p>
<p>
A compiler takes source code as input and outputs a program.
The frontend is the \"input\" part. It brings in your source code, attempts to
understand it, turns it into some sort of internal representation, makes sure
everything is correct and gives errors if the source code has a problem.
</p>
</li>
<li>
<p>
<span style=\"font-weight: bold\">Optimizer:</span>
Optimization is an optional, but very common, step.
It adjusts the program being compiled so it runs faster, or in some cases,
so it takes up less space. Sometimes this is considered to be part of either
the frontend or the backend, or split between both.
</p>
<p>
Automated parsing tools such as Goldie don't help with this step. This has to be
either written manually, or an existing optimizer could be used. Either way,
this can be a fair amount of work.
</p>
</li>
<li>
<p>
<span style=\"font-weight: bold\">Backend:</span>
The (somewhat amusingly-named) backend is the \"output\" part of a compiler.
It takes the internal representation of the code and converts it into either
machine code (possibly for a Virtual Machine) or another programming language.
In the case of generating machine code, there's a lot of associated
computer science theory (see the books in [$pageLink|#More| More Information $]).
</p>
<p>
For many languages, the last part of the backend is the linker. The linker
combines the many different compiled parts of a program (usually one for each
original source file) into one single program. Often, this is done by either a
completely separate program (as with many natively-compiled languages,
such as D or C/C++) or by the host platform itself (as with dynamically-loaded
libraries and many virtual machines such as JVM and .NET).
</p>
<p>
As with the optimizer, automated parsing tools don't help with this step.
The backend has to either be written manually, or an existing backend can be
adapted.
</p>
</li>
</ol>

<a name=\"Frontend\" />
<h3>The Frontend: Lexing, Parsing, AST and Semantics</h3>
<p>
The frontend handles the first step in the compiling process.
Like the compiler itself, the frontend is divided into separate steps:
Lexing (or \"Lexical Analysis\"), Parsing (or \"Grammatical/Syntactical Analysis\"),
AST Creation, and Semantic Analysis.
</p>
<p>
Sometimes people refer to the frontend as a \"parser\", but that's technically
incorrect. The parser is just one of the components in the frontend.
</p>
<div style=\"text-align: center;\">
	<img alt=\"Frontend Diagram\" src=\"[$urlToRoot$]frontend-components.png\" />
</div>
<ol>
<li>
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Lexed Tokens\" src=\"[$urlToRoot$]lex-sample.png\" />
<span style=\"font-weight: bold\">Lexing:</span>
This separates the source into a series of tokens. For instance,
[$code|inline|int numApples = 10$] gets converted into
\"Keyword 'int', Identifier 'numApples', Equals sign, Number 10\".
Goldie does this in the [$typeName|Lexer$] class by using a
[$link| http://goldparser.org/articles/dfa.htm | DFA $].
Lexers are also sometimes called tokenizers and scanners.
You can view the result of this step using the [$pageTitle|Parse$] tool
and [$pageTitle|JsonViewer$].
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Parse Tree\" src=\"[$urlToRoot$]parse-tree-sample.png\" />
<span style=\"font-weight: bold\">Parsing:</span>
This arranges the lexed tokens into a tree. The structure of the tree is
based directly on the rules in the language's grammar.
Goldie does this in the [$typeName|Parser$] class by using an
[$link| http://goldparser.org/articles/lalr.htm | LALR(1) $] algorithm.
You can view the result of this step using the [$pageTitle|Parse$] tool
and [$pageTitle|JsonViewer$].
</p>
<p>
Sometimes parsers don't actually build a real parse tree. They may just simply
process the tokens as they're being parsed. Or they may merge the parsing step
with AST creation (see below) and directly output an AST.
Goldie always builds a parse tree, although a future version of Goldie may
provide the ability to omit it.
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Abstract Syntax Tree\" src=\"[$urlToRoot$]ast-sample.png\" />
<span style=\"font-weight: bold\">AST Creation:</span>
This step is optional and is only sometimes performed by automatic parsers.
Goldie doesn't currently perform this (so you'll have to do it yourself if you want an AST),
but it probably will in a future version. Sometimes this is considered
part of either the parsing step or the semantic analysis step.
</p>
<p>
In this step, the parse tree is converted into an AST (Abstract Syntax Tree).
An AST is like a parse tree, but it more closely resembles the way
humans understand the code. For instance, the parse tree representation of
[$code|inline| 5 + 10 $] can be somewhat complex, unintuitive and highly
dependent on the language's grammar. But an AST would most likely represent it
very naturally: With one node for \"Addition\" that contains two subnodes,
one for \"5\" and one for \"10\".
</p>
<p>
An XML/HTML DOM is a good example of an AST. For another example, see the output
of [$pageTitle|GenDocs$]'s [$code|inline|-ast$] flag.
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Semantic Analysis\" src=\"[$urlToRoot$]semanitc-sample.png\" />
<span style=\"font-weight: bold\">Semantic Analysis:</span>
This step is generally NOT performed by automatic parsers.
The user of such tools has to perform this step on their own because it's
not as easily formalized as lexing, parsing or AST creation.
</p>
<p>
In this step, the parse tree or the AST is analyzed and actual meaning is
determined. This often involves extra error
checking. For instance, in statically-typed languages, the type system exists
in the semantic analysis phase. This step is also where type-mismatch errors
and \"undefined function/variable\" errors are generated. Semantic analysis can
be thought of as anything in the frontend that isn't formally defined
by the language's grammar.
</p>
<p>
See the
[$link| https://bitbucket.org/Abscissa/goldie/src/v0.8/src/tools/gendocs | GenDocs source $]
for an example of lexing/parsing with Goldie and then constructing an AST tree
and performing semantic analysis.
</p>
</li>
</ol>

<a name=\"ParsingTool\" />
<h3 style=\"clear: both;\">Using a Parsing Tool</h3>
<p>
Parsing tools such as Goldie only deal with the frontend. But not the entire
frontend: Just the lexing, parsing, and sometimes AST creation parts.
The rest still has to be written by the user of the parsing tool.
</p>
<p>
There are a variety of parsing tools available, and they differ in various ways,
such as: what parsing algorithm they use, what language is used to perform the
parsing (ie, the \"host\" language), how the grammar is defined, and what special
tools can be used.
</p>
<p>
Goldie is compatible with the
[$pageLink|OtherTools#GOLD| GOLD Parsing System $], and both use
[$link| http://goldparser.org/articles/dfa.htm | DFA $]
for lexing and
[$link| http://goldparser.org/articles/lalr.htm | LALR(1) $]
for parsing. GoldieLib is designed to be used in programs written in the
[$link| http://www.d-programming-language.org/ | D programming language $]
(D version 2). But, the GOLD/Goldie systems
are designed to be easily extended to other host languages via GOLD-compatible
\"engines\",
[$link| http://goldparser.org/engine/index.htm | many of which are available $]
besides GoldieLib.
</p>
<p>
See the [$pageTitle|Overview$] page for an overview of using Goldie, or
the [$pageTitle|Tutorial$] page for a full tutorial.
</p>
<p>
The GOLD website has a great tutorial on 
[$link| http://goldparser.org/getting-started/index.htm | Getting Started With Parsing $]
that's geared towards GOLD. It's applicable to Goldie as well, since the two are compatible.
</p>

<a name=\"Next\" />
<h3>The Next Step</h3>
<p>
<em>Next:</em> [$pageTitle|Overview$]
</p>
<p>
Or, skip to the [$pageTitle|Tutorial$].
</p>

<a name=\"More\" />
<h3>More Information</h3>
<p>
There are many resources for learning more about compilers and the
computer science theory behind them. Here are some recommended
resources for getting started:
</p>
<h4 style=\"margin-bottom: 5px;\">Web Pages:</h4>
<ul>
<li style=\"margin-bottom: 7px;\">
	[$link| http://goldparser.org/articles/index.htm | GOLD Parsing System: Articles, Links and Much More $]
	<br />
	Many useful articles and links. I've personally found these very helpful.
</li>
</ul>
<h4 style=\"margin-bottom: 5px;\">Books:</h4>
<ul>
<li style=\"margin-bottom: 7px;\">
	[$link| http://www.pearsonhighered.com/educator/product/Crafting-A-Compiler/9780136067054.page | Crafting a Compiler $]
	<br />
	<span style=\"font-style: italic; font-size: 0.95em;\">
	ISBN-10: 0136067050<br />
	ISBN-13: 978-0136067054<br />
	</span>
	All books on compiler theory I've seen target an audience of
	mathematicians, computer scientists and/or students of such fields, rather
	than programmers. But this
	is by far the most programmer-friendly one I've come across.
	I found it to be of immense help when writing [$pageTitle|GRMC$].
</li>
<li style=\"margin-bottom: 7px;\">
	[$link| http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools | Compilers: Principles, Techniques, and Tools $]
	(ie, \"The Dragon Book\")
	<br />
	<span style=\"font-style: italic; font-size: 0.95em;\">
	ISBN-10: 0321486811<br />
	ISBN-13: 978-0321486813<br />
	</span>
	Widely considered the classic text on compiler theory. It is, however,
	one of the most heavily mathematician/computer-scientist-oriented
	compiler books out there.
	But, while it's far from being the most programmer-friendly,
	it is very detailed and thorough.
</li>
<li style=\"margin-bottom: 7px;\">
	[$link| http://goldparser.org/articles/other-parsers.htm | GOLD Parsing System: Compiler Books $]
	<br />
	Links to some other books on compiler theory, and also other parsing systems.
</li>
</ul>
", 
		"0: name": {
			"srcIndexStart": "0", 
			"data": "LearnParsing", 
			"srcLength": "21", 
			"0: data": {
				"srcIndexStart": "7", 
				"data": "LearnParsing", 
				"srcLength": "12"
			}
		}, 
		"1: data": {
			"srcIndexStart": "21", 
			"data": "
", 
			"srcLength": "2"
		}, 
		"2: title": {
			"srcIndexStart": "23", 
			"data": "Never Used a Parsing Tool?", 
			"srcLength": "36", 
			"0: data": {
				"srcIndexStart": "31", 
				"data": "Never Used a Parsing Tool?", 
				"srcLength": "26"
			}
		}, 
		"3: data": {
			"srcIndexStart": "59", 
			"data": "
", 
			"srcLength": "2"
		}, 
		"4: frame": {
			"srcIndexStart": "61", 
			"data": "HTMLPage.tmpl", 
			"srcLength": "23", 
			"0: data": {
				"srcIndexStart": "69", 
				"data": "HTMLPage.tmpl", 
				"srcLength": "13"
			}
		}, 
		"5: data": {
			"srcIndexStart": "84", 
			"data": "

<ul>
<li>", 
			"srcLength": "14"
		}, 
		"6: pageLink": {
			"srcIndexStart": "98", 
			"param 0": "#Compilers", 
			"data": "How a Compiler Works", 
			"srcLength": "48", 
			"0: data": {
				"srcIndexStart": "120", 
				"data": "How a Compiler Works", 
				"srcLength": "24"
			}
		}, 
		"7: data": {
			"srcIndexStart": "146", 
			"data": "</li>
<li>", 
			"srcLength": "11"
		}, 
		"8: pageLink": {
			"srcIndexStart": "157", 
			"param 0": "#Frontend", 
			"data": "The Frontend: Lexing, Parsing, AST and Semantics", 
			"srcLength": "76", 
			"0: data": {
				"srcIndexStart": "178", 
				"data": "The Frontend: Lexing, Parsing, AST and Semantics", 
				"srcLength": "53"
			}
		}, 
		"9: data": {
			"srcIndexStart": "233", 
			"data": "</li>
<li>", 
			"srcLength": "11"
		}, 
		"10: pageLink": {
			"srcIndexStart": "244", 
			"param 0": "#ParsingTool", 
			"data": "Using a Parsing Tool", 
			"srcLength": "48", 
			"0: data": {
				"srcIndexStart": "268", 
				"data": "Using a Parsing Tool", 
				"srcLength": "22"
			}
		}, 
		"11: data": {
			"srcIndexStart": "292", 
			"data": "</li>
<li>", 
			"srcLength": "11"
		}, 
		"12: pageLink": {
			"srcIndexStart": "303", 
			"param 0": "#Next", 
			"data": "The Next Step", 
			"srcLength": "48", 
			"0: data": {
				"srcIndexStart": "320", 
				"data": "The Next Step", 
				"srcLength": "29"
			}
		}, 
		"13: data": {
			"srcIndexStart": "351", 
			"data": "</li>
<li>", 
			"srcLength": "11"
		}, 
		"14: pageLink": {
			"srcIndexStart": "362", 
			"param 0": "#More", 
			"data": "More Information", 
			"srcLength": "48", 
			"0: data": {
				"srcIndexStart": "379", 
				"data": "More Information", 
				"srcLength": "29"
			}
		}, 
		"15: data": {
			"srcIndexStart": "410", 
			"data": "</li>
</ul>

<a name=\"Compilers\" />
<h3 style=\"margin-bottom: 0px;\">How a Compiler Works</h3>
<h4 style=\"margin-top: 0px;\">(Or: How can I use Goldie to create a compiler?)</h4>
<p>
There's a common misconception that language tools and computer science
theory have advanced enough that creating a compiler can be fully-automated.
This is not true. Only <em>certain parts</em> of writing a compiler can be
automated, and it's only these parts that parsing tools (such as Goldie, GOLD,
Lex/YACC, Flex/Bison and ANTLR) automate. A fully-working compiler is a
complex program that contains many different parts.
</p>
<p>
Here is a diagram of the three main parts of a compiler:
</p>
<div style=\"text-align: center;\">
	<img alt=\"Compiler Diagram\" src=\"", 
			"srcLength": "765"
		}, 
		"16: var": {
			"srcIndexStart": "1175", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"17: data": {
			"srcIndexStart": "1188", 
			"data": "compiler-components.png\" />
</div>
<ol>
<li>
<p>
<span style=\"font-weight: bold\">Frontend:</span>
This is the only part of a compiler that automated parsing tools deal with.
Even so, automated parsing tools only deal with <em>part</em> of the frontend
(see the section
", 
			"srcLength": "278"
		}, 
		"18: pageLink": {
			"srcIndexStart": "1466", 
			"param 0": "#Frontend", 
			"data": "The Frontend: Lexing, Parsing, AST and Semantics", 
			"srcLength": "71", 
			"0: data": {
				"srcIndexStart": "1487", 
				"data": "The Frontend: Lexing, Parsing, AST and Semantics", 
				"srcLength": "48"
			}
		}, 
		"19: data": {
			"srcIndexStart": "1537", 
			"data": "
below).
</p>
<p>
A compiler takes source code as input and outputs a program.
The frontend is the \"input\" part. It brings in your source code, attempts to
understand it, turns it into some sort of internal representation, makes sure
everything is correct and gives errors if the source code has a problem.
</p>
</li>
<li>
<p>
<span style=\"font-weight: bold\">Optimizer:</span>
Optimization is an optional, but very common, step.
It adjusts the program being compiled so it runs faster, or in some cases,
so it takes up less space. Sometimes this is considered to be part of either
the frontend or the backend, or split between both.
</p>
<p>
Automated parsing tools such as Goldie don't help with this step. This has to be
either written manually, or an existing optimizer could be used. Either way,
this can be a fair amount of work.
</p>
</li>
<li>
<p>
<span style=\"font-weight: bold\">Backend:</span>
The (somewhat amusingly-named) backend is the \"output\" part of a compiler.
It takes the internal representation of the code and converts it into either
machine code (possibly for a Virtual Machine) or another programming language.
In the case of generating machine code, there's a lot of associated
computer science theory (see the books in ", 
			"srcLength": "1275"
		}, 
		"20: pageLink": {
			"srcIndexStart": "2812", 
			"param 0": "#More", 
			"data": "More Information", 
			"srcLength": "37", 
			"0: data": {
				"srcIndexStart": "2829", 
				"data": "More Information", 
				"srcLength": "18"
			}
		}, 
		"21: data": {
			"srcIndexStart": "2849", 
			"data": ").
</p>
<p>
For many languages, the last part of the backend is the linker. The linker
combines the many different compiled parts of a program (usually one for each
original source file) into one single program. Often, this is done by either a
completely separate program (as with many natively-compiled languages,
such as D or C/C++) or by the host platform itself (as with dynamically-loaded
libraries and many virtual machines such as JVM and .NET).
</p>
<p>
As with the optimizer, automated parsing tools don't help with this step.
The backend has to either be written manually, or an existing backend can be
adapted.
</p>
</li>
</ol>

<a name=\"Frontend\" />
<h3>The Frontend: Lexing, Parsing, AST and Semantics</h3>
<p>
The frontend handles the first step in the compiling process.
Like the compiler itself, the frontend is divided into separate steps:
Lexing (or \"Lexical Analysis\"), Parsing (or \"Grammatical/Syntactical Analysis\"),
AST Creation, and Semantic Analysis.
</p>
<p>
Sometimes people refer to the frontend as a \"parser\", but that's technically
incorrect. The parser is just one of the components in the frontend.
</p>
<div style=\"text-align: center;\">
	<img alt=\"Frontend Diagram\" src=\"", 
			"srcLength": "1234"
		}, 
		"22: var": {
			"srcIndexStart": "4083", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"23: data": {
			"srcIndexStart": "4096", 
			"data": "frontend-components.png\" />
</div>
<ol>
<li>
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Lexed Tokens\" src=\"", 
			"srcLength": "163"
		}, 
		"24: var": {
			"srcIndexStart": "4259", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"25: data": {
			"srcIndexStart": "4272", 
			"data": "lex-sample.png\" />
<span style=\"font-weight: bold\">Lexing:</span>
This separates the source into a series of tokens. For instance,
", 
			"srcLength": "134"
		}, 
		"26: code": {
			"srcIndexStart": "4406", 
			"param 0": "inline", 
			"data": "int numApples = 10", 
			"srcLength": "34", 
			"0: data": {
				"srcIndexStart": "4420", 
				"data": "int numApples = 10", 
				"srcLength": "18"
			}
		}, 
		"27: data": {
			"srcIndexStart": "4440", 
			"data": " gets converted into
\"Keyword 'int', Identifier 'numApples', Equals sign, Number 10\".
Goldie does this in the ", 
			"srcLength": "112"
		}, 
		"28: typeName": {
			"srcIndexStart": "4552", 
			"data": "Lexer", 
			"srcLength": "18", 
			"0: data": {
				"srcIndexStart": "4563", 
				"data": "Lexer", 
				"srcLength": "5"
			}
		}, 
		"29: data": {
			"srcIndexStart": "4570", 
			"data": " class by using a
", 
			"srcLength": "19"
		}, 
		"30: link": {
			"srcIndexStart": "4589", 
			"param 0": "http://goldparser.org/articles/dfa.htm", 
			"data": "DFA", 
			"srcLength": "55", 
			"0: data": {
				"srcIndexStart": "4637", 
				"data": "DFA", 
				"srcLength": "5"
			}
		}, 
		"31: data": {
			"srcIndexStart": "4644", 
			"data": ".
Lexers are also sometimes called tokenizers and scanners.
You can view the result of this step using the ", 
			"srcLength": "109"
		}, 
		"32: pageTitle": {
			"srcIndexStart": "4753", 
			"data": "Parse", 
			"srcLength": "19", 
			"0: data": {
				"srcIndexStart": "4765", 
				"data": "Parse", 
				"srcLength": "5"
			}
		}, 
		"33: data": {
			"srcIndexStart": "4772", 
			"data": " tool
and ", 
			"srcLength": "11"
		}, 
		"34: pageTitle": {
			"srcIndexStart": "4783", 
			"data": "JsonViewer", 
			"srcLength": "24", 
			"0: data": {
				"srcIndexStart": "4795", 
				"data": "JsonViewer", 
				"srcLength": "10"
			}
		}, 
		"35: data": {
			"srcIndexStart": "4807", 
			"data": ".
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Parse Tree\" src=\"", 
			"srcLength": "155"
		}, 
		"36: var": {
			"srcIndexStart": "4962", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"37: data": {
			"srcIndexStart": "4975", 
			"data": "parse-tree-sample.png\" />
<span style=\"font-weight: bold\">Parsing:</span>
This arranges the lexed tokens into a tree. The structure of the tree is
based directly on the rules in the language's grammar.
Goldie does this in the ", 
			"srcLength": "230"
		}, 
		"38: typeName": {
			"srcIndexStart": "5205", 
			"data": "Parser", 
			"srcLength": "19", 
			"0: data": {
				"srcIndexStart": "5216", 
				"data": "Parser", 
				"srcLength": "6"
			}
		}, 
		"39: data": {
			"srcIndexStart": "5224", 
			"data": " class by using an
", 
			"srcLength": "20"
		}, 
		"40: link": {
			"srcIndexStart": "5244", 
			"param 0": "http://goldparser.org/articles/lalr.htm", 
			"data": "LALR(1)", 
			"srcLength": "60", 
			"0: data": {
				"srcIndexStart": "5293", 
				"data": "LALR(1)", 
				"srcLength": "9"
			}
		}, 
		"41: data": {
			"srcIndexStart": "5304", 
			"data": " algorithm.
You can view the result of this step using the ", 
			"srcLength": "60"
		}, 
		"42: pageTitle": {
			"srcIndexStart": "5364", 
			"data": "Parse", 
			"srcLength": "19", 
			"0: data": {
				"srcIndexStart": "5376", 
				"data": "Parse", 
				"srcLength": "5"
			}
		}, 
		"43: data": {
			"srcIndexStart": "5383", 
			"data": " tool
and ", 
			"srcLength": "11"
		}, 
		"44: pageTitle": {
			"srcIndexStart": "5394", 
			"data": "JsonViewer", 
			"srcLength": "24", 
			"0: data": {
				"srcIndexStart": "5406", 
				"data": "JsonViewer", 
				"srcLength": "10"
			}
		}, 
		"45: data": {
			"srcIndexStart": "5418", 
			"data": ".
</p>
<p>
Sometimes parsers don't actually build a real parse tree. They may just simply
process the tokens as they're being parsed. Or they may merge the parsing step
with AST creation (see below) and directly output an AST.
Goldie always builds a parse tree, although a future version of Goldie may
provide the ability to omit it.
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Abstract Syntax Tree\" src=\"", 
			"srcLength": "504"
		}, 
		"46: var": {
			"srcIndexStart": "5922", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"47: data": {
			"srcIndexStart": "5935", 
			"data": "ast-sample.png\" />
<span style=\"font-weight: bold\">AST Creation:</span>
This step is optional and is only sometimes performed by automatic parsers.
Goldie doesn't currently perform this (so you'll have to do it yourself if you want an AST),
but it probably will in a future version. Sometimes this is considered
part of either the parsing step or the semantic analysis step.
</p>
<p>
In this step, the parse tree is converted into an AST (Abstract Syntax Tree).
An AST is like a parse tree, but it more closely resembles the way
humans understand the code. For instance, the parse tree representation of
", 
			"srcLength": "615"
		}, 
		"48: code": {
			"srcIndexStart": "6550", 
			"param 0": "inline", 
			"data": "5 + 10", 
			"srcLength": "24", 
			"0: data": {
				"srcIndexStart": "6564", 
				"data": "5 + 10", 
				"srcLength": "8"
			}
		}, 
		"49: data": {
			"srcIndexStart": "6574", 
			"data": " can be somewhat complex, unintuitive and highly
dependent on the language's grammar. But an AST would most likely represent it
very naturally: With one node for \"Addition\" that contains two subnodes,
one for \"5\" and one for \"10\".
</p>
<p>
An XML/HTML DOM is a good example of an AST. For another example, see the output
of ", 
			"srcLength": "331"
		}, 
		"50: pageTitle": {
			"srcIndexStart": "6905", 
			"data": "GenDocs", 
			"srcLength": "21", 
			"0: data": {
				"srcIndexStart": "6917", 
				"data": "GenDocs", 
				"srcLength": "7"
			}
		}, 
		"51: data": {
			"srcIndexStart": "6926", 
			"data": "'s ", 
			"srcLength": "3"
		}, 
		"52: code": {
			"srcIndexStart": "6929", 
			"param 0": "inline", 
			"data": "-ast", 
			"srcLength": "20", 
			"0: data": {
				"srcIndexStart": "6943", 
				"data": "-ast", 
				"srcLength": "4"
			}
		}, 
		"53: data": {
			"srcIndexStart": "6949", 
			"data": " flag.
</p>
</li>
<li style=\"clear: both;\">
<p>
<img style=\"float: right; border: 1px solid black; margin: 0px 0px 8px 5px;\" alt=\"Example Semantic Analysis\" src=\"", 
			"srcLength": "167"
		}, 
		"54: var": {
			"srcIndexStart": "7116", 
			"param 0": "urlToRoot", 
			"srcLength": "13"
		}, 
		"55: data": {
			"srcIndexStart": "7129", 
			"data": "semanitc-sample.png\" />
<span style=\"font-weight: bold\">Semantic Analysis:</span>
This step is generally NOT performed by automatic parsers.
The user of such tools has to perform this step on their own because it's
not as easily formalized as lexing, parsing or AST creation.
</p>
<p>
In this step, the parse tree or the AST is analyzed and actual meaning is
determined. This often involves extra error
checking. For instance, in statically-typed languages, the type system exists
in the semantic analysis phase. This step is also where type-mismatch errors
and \"undefined function/variable\" errors are generated. Semantic analysis can
be thought of as anything in the frontend that isn't formally defined
by the language's grammar.
</p>
<p>
See the
", 
			"srcLength": "767"
		}, 
		"56: link": {
			"srcIndexStart": "7896", 
			"param 0": "https://bitbucket.org/Abscissa/goldie/src/v0.8/src/tools/gendocs", 
			"data": "GenDocs source", 
			"srcLength": "92", 
			"0: data": {
				"srcIndexStart": "7970", 
				"data": "GenDocs source", 
				"srcLength": "16"
			}
		}, 
		"57: data": {
			"srcIndexStart": "7988", 
			"data": "
for an example of lexing/parsing with Goldie and then constructing an AST tree
and performing semantic analysis.
</p>
</li>
</ol>

<a name=\"ParsingTool\" />
<h3 style=\"clear: both;\">Using a Parsing Tool</h3>
<p>
Parsing tools such as Goldie only deal with the frontend. But not the entire
frontend: Just the lexing, parsing, and sometimes AST creation parts.
The rest still has to be written by the user of the parsing tool.
</p>
<p>
There are a variety of parsing tools available, and they differ in various ways,
such as: what parsing algorithm they use, what language is used to perform the
parsing (ie, the \"host\" language), how the grammar is defined, and what special
tools can be used.
</p>
<p>
Goldie is compatible with the
", 
			"srcLength": "754"
		}, 
		"58: pageLink": {
			"srcIndexStart": "8742", 
			"param 0": "OtherTools#GOLD", 
			"data": "GOLD Parsing System", 
			"srcLength": "50", 
			"0: data": {
				"srcIndexStart": "8769", 
				"data": "GOLD Parsing System", 
				"srcLength": "21"
			}
		}, 
		"59: data": {
			"srcIndexStart": "8792", 
			"data": ", and both use
", 
			"srcLength": "16"
		}, 
		"60: link": {
			"srcIndexStart": "8808", 
			"param 0": "http://goldparser.org/articles/dfa.htm", 
			"data": "DFA", 
			"srcLength": "55", 
			"0: data": {
				"srcIndexStart": "8856", 
				"data": "DFA", 
				"srcLength": "5"
			}
		}, 
		"61: data": {
			"srcIndexStart": "8863", 
			"data": "
for lexing and
", 
			"srcLength": "18"
		}, 
		"62: link": {
			"srcIndexStart": "8881", 
			"param 0": "http://goldparser.org/articles/lalr.htm", 
			"data": "LALR(1)", 
			"srcLength": "60", 
			"0: data": {
				"srcIndexStart": "8930", 
				"data": "LALR(1)", 
				"srcLength": "9"
			}
		}, 
		"63: data": {
			"srcIndexStart": "8941", 
			"data": "
for parsing. GoldieLib is designed to be used in programs written in the
", 
			"srcLength": "76"
		}, 
		"64: link": {
			"srcIndexStart": "9017", 
			"param 0": "http://www.d-programming-language.org/", 
			"data": "D programming language", 
			"srcLength": "74", 
			"0: data": {
				"srcIndexStart": "9065", 
				"data": "D programming language", 
				"srcLength": "24"
			}
		}, 
		"65: data": {
			"srcIndexStart": "9091", 
			"data": "
(D version 2). But, the GOLD/Goldie systems
are designed to be easily extended to other host languages via GOLD-compatible
\"engines\",
", 
			"srcLength": "139"
		}, 
		"66: link": {
			"srcIndexStart": "9230", 
			"param 0": "http://goldparser.org/engine/index.htm", 
			"data": "many of which are available", 
			"srcLength": "79", 
			"0: data": {
				"srcIndexStart": "9278", 
				"data": "many of which are available", 
				"srcLength": "29"
			}
		}, 
		"67: data": {
			"srcIndexStart": "9309", 
			"data": "
besides GoldieLib.
</p>
<p>
See the ", 
			"srcLength": "41"
		}, 
		"68: pageTitle": {
			"srcIndexStart": "9350", 
			"data": "Overview", 
			"srcLength": "22", 
			"0: data": {
				"srcIndexStart": "9362", 
				"data": "Overview", 
				"srcLength": "8"
			}
		}, 
		"69: data": {
			"srcIndexStart": "9372", 
			"data": " page for an overview of using Goldie, or
the ", 
			"srcLength": "47"
		}, 
		"70: pageTitle": {
			"srcIndexStart": "9419", 
			"data": "Tutorial", 
			"srcLength": "22", 
			"0: data": {
				"srcIndexStart": "9431", 
				"data": "Tutorial", 
				"srcLength": "8"
			}
		}, 
		"71: data": {
			"srcIndexStart": "9441", 
			"data": " page for a full tutorial.
</p>
<p>
The GOLD website has a great tutorial on 
", 
			"srcLength": "82"
		}, 
		"72: link": {
			"srcIndexStart": "9523", 
			"param 0": "http://goldparser.org/getting-started/index.htm", 
			"data": "Getting Started With Parsing", 
			"srcLength": "89", 
			"0: data": {
				"srcIndexStart": "9580", 
				"data": "Getting Started With Parsing", 
				"srcLength": "30"
			}
		}, 
		"73: data": {
			"srcIndexStart": "9612", 
			"data": "
that's geared towards GOLD. It's applicable to Goldie as well, since the two are compatible.
</p>

<a name=\"Next\" />
<h3>The Next Step</h3>
<p>
<em>Next:</em> ", 
			"srcLength": "167"
		}, 
		"74: pageTitle": {
			"srcIndexStart": "9779", 
			"data": "Overview", 
			"srcLength": "22", 
			"0: data": {
				"srcIndexStart": "9791", 
				"data": "Overview", 
				"srcLength": "8"
			}
		}, 
		"75: data": {
			"srcIndexStart": "9801", 
			"data": "
</p>
<p>
Or, skip to the ", 
			"srcLength": "29"
		}, 
		"76: pageTitle": {
			"srcIndexStart": "9830", 
			"data": "Tutorial", 
			"srcLength": "22", 
			"0: data": {
				"srcIndexStart": "9842", 
				"data": "Tutorial", 
				"srcLength": "8"
			}
		}, 
		"77: data": {
			"srcIndexStart": "9852", 
			"data": ".
</p>

<a name=\"More\" />
<h3>More Information</h3>
<p>
There are many resources for learning more about compilers and the
computer science theory behind them. Here are some recommended
resources for getting started:
</p>
<h4 style=\"margin-bottom: 5px;\">Web Pages:</h4>
<ul>
<li style=\"margin-bottom: 7px;\">
	", 
			"srcLength": "322"
		}, 
		"78: link": {
			"srcIndexStart": "10174", 
			"param 0": "http://goldparser.org/articles/index.htm", 
			"data": "GOLD Parsing System: Articles, Links and Much More", 
			"srcLength": "104", 
			"0: data": {
				"srcIndexStart": "10224", 
				"data": "GOLD Parsing System: Articles, Links and Much More", 
				"srcLength": "52"
			}
		}, 
		"79: data": {
			"srcIndexStart": "10278", 
			"data": "
	<br />
	Many useful articles and links. I've personally found these very helpful.
</li>
</ul>
<h4 style=\"margin-bottom: 5px;\">Books:</h4>
<ul>
<li style=\"margin-bottom: 7px;\">
	", 
			"srcLength": "187"
		}, 
		"80: link": {
			"srcIndexStart": "10465", 
			"param 0": "http://www.pearsonhighered.com/educator/product/Crafting-A-Compiler/9780136067054.page", 
			"data": "Crafting a Compiler", 
			"srcLength": "119", 
			"0: data": {
				"srcIndexStart": "10561", 
				"data": "Crafting a Compiler", 
				"srcLength": "21"
			}
		}, 
		"81: data": {
			"srcIndexStart": "10584", 
			"data": "
	<br />
	<span style=\"font-style: italic; font-size: 0.95em;\">
	ISBN-10: 0136067050<br />
	ISBN-13: 978-0136067054<br />
	</span>
	All books on compiler theory I've seen target an audience of
	mathematicians, computer scientists and/or students of such fields, rather
	than programmers. But this
	is by far the most programmer-friendly one I've come across.
	I found it to be of immense help when writing ", 
			"srcLength": "416"
		}, 
		"82: pageTitle": {
			"srcIndexStart": "11000", 
			"data": "GRMC", 
			"srcLength": "18", 
			"0: data": {
				"srcIndexStart": "11012", 
				"data": "GRMC", 
				"srcLength": "4"
			}
		}, 
		"83: data": {
			"srcIndexStart": "11018", 
			"data": ".
</li>
<li style=\"margin-bottom: 7px;\">
	", 
			"srcLength": "45"
		}, 
		"84: link": {
			"srcIndexStart": "11063", 
			"param 0": "http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools", 
			"data": "Compilers: Principles, Techniques, and Tools", 
			"srcLength": "131", 
			"0: data": {
				"srcIndexStart": "11146", 
				"data": "Compilers: Principles, Techniques, and Tools", 
				"srcLength": "46"
			}
		}, 
		"85: data": {
			"srcIndexStart": "11194", 
			"data": "
	(ie, \"The Dragon Book\")
	<br />
	<span style=\"font-style: italic; font-size: 0.95em;\">
	ISBN-10: 0321486811<br />
	ISBN-13: 978-0321486813<br />
	</span>
	Widely considered the classic text on compiler theory. It is, however,
	one of the most heavily mathematician/computer-scientist-oriented
	compiler books out there.
	But, while it's far from being the most programmer-friendly,
	it is very detailed and thorough.
</li>
<li style=\"margin-bottom: 7px;\">
	", 
			"srcLength": "473"
		}, 
		"86: link": {
			"srcIndexStart": "11667", 
			"param 0": "http://goldparser.org/articles/other-parsers.htm", 
			"data": "GOLD Parsing System: Compiler Books", 
			"srcLength": "97", 
			"0: data": {
				"srcIndexStart": "11725", 
				"data": "GOLD Parsing System: Compiler Books", 
				"srcLength": "37"
			}
		}, 
		"87: data": {
			"srcIndexStart": "11764", 
			"data": "
	<br />
	Links to some other books on compiler theory, and also other parsing systems.
</li>
</ul>", 
			"srcLength": "105"
		}
	}
}