Parser - Revision history

Adamcolton at 20:51, 21 June 2017

2017-06-21T20:51:36Z

← Older revision		Revision as of 20:51, 21 June 2017
Line 8:		Line 8:

	https://stackoverflow.com/questions/4931346/how-to-output-the-ast-built-using-antlr		https://stackoverflow.com/questions/4931346/how-to-output-the-ast-built-using-antlr

			https://tomassetti.me/domain-specific-languages/#textual_languages

	== Top Down ==		== Top Down ==

Adamcolton at 20:47, 21 June 2017

2017-06-21T20:47:31Z

← Older revision		Revision as of 20:47, 21 June 2017
Line 6:		Line 6:

	I'm not very worried about efficiency, at least not right now.		I'm not very worried about efficiency, at least not right now.

			https://stackoverflow.com/questions/4931346/how-to-output-the-ast-built-using-antlr

	== Top Down ==		== Top Down ==

Adamcolton at 21:10, 15 February 2017

2017-02-15T21:10:21Z

← Older revision		Revision as of 21:10, 15 February 2017
Line 6:		Line 6:

	I'm not very worried about efficiency, at least not right now.		I'm not very worried about efficiency, at least not right now.

			== Top Down ==
			I could just calm the fuck down and use a top-down parser. Sure, I can't do left recursion, but it's easy to write a grammar to avoid it. And I could start experimenting with using the parser before writing a bottom up parser.

			I think I'll do this for now and keep working on the FA stuff and eventually build a shift-reduce parser.

	== FA ==		== FA ==

Adamcolton: /* Packrat Parser */

2017-02-15T00:06:23Z

Packrat Parser

← Older revision		Revision as of 00:06, 15 February 2017
Line 19:		Line 19:
	This https://github.com/pointlander/peg could be an example, but it's build as a damn CLI instead of pulling the guts into a package. I might fork it and do a pull request.		This https://github.com/pointlander/peg could be an example, but it's build as a damn CLI instead of pulling the guts into a package. I might fork it and do a pull request.

			Hrm... looks like it still can't handle left recursion. I kind of want that.

	== Bottom Up ==		== Bottom Up ==

Adamcolton at 18:36, 14 February 2017

2017-02-14T18:36:26Z

← Older revision		Revision as of 18:36, 14 February 2017
Line 16:		Line 16:
	== Packrat Parser ==		== Packrat Parser ==
	A variant of top down.		A variant of top down.

			This https://github.com/pointlander/peg could be an example, but it's build as a damn CLI instead of pulling the guts into a package. I might fork it and do a pull request.


	== Bottom Up ==		== Bottom Up ==

Adamcolton at 18:28, 14 February 2017

2017-02-14T18:28:55Z

← Older revision		Revision as of 18:28, 14 February 2017
Line 33:		Line 33:
	A2 → DA0		A2 → DA0
	A0 → ε		A0 → ε

			And then write a corresponding routine to recover the original parse tree.

	[[Category:Code]]		[[Category:Code]]

Adamcolton at 18:28, 14 February 2017

2017-02-14T18:28:11Z

← Older revision		Revision as of 18:28, 14 February 2017
Line 21:		Line 21:

	=== CYK ===		=== CYK ===
	This algorithm looks pretty simple, but it requires that notation be in Chomsky Normalized Form, A → BC or A → α		This algorithm looks pretty simple, but it requires that notation be in Chomsky Normalized Form, A → BC or A → α, but it might be easier to do something like this:
			A → BCDE
			To
			A → A1A2
			A1 → BC
			A2 → DE
			or
			A → BCD
			A → A1A2
			A1 → BC
			A2 → DA0
			A0 → ε

	[[Category:Code]]		[[Category:Code]]

Adamcolton: Created page with "I want to build a generic context-free Parser in Go. I've already built a lexer, though it may need some work. I build a top down parser, but it only produces an equivalent ..."

2017-02-14T18:25:01Z

Created page with "I want to build a generic context-free Parser in Go. I've already built a lexer, though it may need some work. I build a top down parser, but it only produces an equivalent ..."

New page

I want to build a generic context-free Parser in Go.

I've already built a lexer, though it may need some work.

I build a top down parser, but it only produces an equivalent parse tree, which doesn't quite work and I haven't been able to figure out how to convert it back to the actual parse tree.

I'm not very worried about efficiency, at least not right now.

== FA ==
I really should build a DFA/NFA library. I started on one, but it ends up more complicated than one would expect.

In Go the real tough part is that I'd like to be able to handle different node/transition types (string/rune, int/int, int/rune) but that gets kind of tricky. I could treat everything as []byte and use crc32 vals for keys in maps.

If I had this, I could build a light weight regex library which would be great for the lexer.

== Packrat Parser ==
A variant of top down.

== Bottom Up ==
This is a whole class of parser, most of which use FA.

=== CYK ===
This algorithm looks pretty simple, but it requires that notation be in Chomsky Normalized Form, A → BC or A → α

[[Category:Code]]