How does Lexer/Parser work in a 2D programming language like Funciton in order to transform such an unusual source-code to the correct AST?
-
2From the link in your question: bitbucket.org/Timwi/funciton-interpreter/src, I imagine you can find your answer in the application's source. I'd hazard a guess you could use edge detection algorithms to find the vertexes, and once you have those finding the edges between them is a fairly straightforward search. Once you have those, you can build a graph, and you're in well tread territory. I don't know if this is how Funciton works, but it would be my first thought.– PhoshiMay 14, 2014 at 8:21
-
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask– gnatMay 14, 2014 at 9:09
2 Answers
Layout sensitive languages are an unusual occurrence because they are a bit more difficult to parse. A token produced by a lexer will not only contain a type and a value, but also a position and maybe a size. It is possible that the lexer will not proceed linearly line by line, but will first read the whole file into memory and then traverse it as a 2D map.
Layout-sensitive parsing or indentation-sensitive parsing is a small but still active field of research; investigating these terms will provide you with a number of papers. In easy cases like Python, we can use a stateful lexer that hides the indentation from a parser, and instead emits phantom tokens like INDENT
and DEDENT
which would be the equivalent to curly braces in C. In more complex cases, we need to annotate the parser's grammar with requirements on the indentation, e.g. the enhanced context free grammar
DoExpression{n} ::= "do"{n} DoExpressionInner{m: m > n}
DoExpressionInner{n} ::= Expression{n}+
might allow
do expr1
expr2
expr3
but not
do expr1
expr2
expr3
In the above grammar, the expression in curly braces puts a condition on the position of the left edge of the rule or token. Most parser generators do not support such layout parsing.
In the most general case, a lexer would have to recognize shapes in the textual input. A parser would then likely use bottom-up techniques to group the primitive shapes into a usable data structure, likely a non-hierarchical graph. For example, the image
012345678901234567890123456789
0 +---+
1 | A |-----------.
2 +---+ | +---+
3 '------->| B |
4 +---+
could be lexed as:
BOX "A" at ( 0, 0) to ( 4, 2)
BOX "B" at (25, 2) to (29, 4)
ARROW at ( 5, 1) to (24, 3)
These tokens could then be stored in a manner supporting spatial lookup. Starting with the A
box, we can look at the surrounding fields and will find the start of the arrow. At the end of the arrow, we find the B
box and can therefore add this connection between A
and B
to the Abstract Syntax Graph. After that, the arrow can be removed from the set of unused tokens. As no other tokens are in the A
box's immediate neighborhood, it too can be removed, ditto for B
. As the set of uninspected tokens is empty, the parse has succeeded.
Parsing Funciton is easier than parsing such ASCII art, as the used symbols directly show connections. It might therefore be possible to parse the source in a single pass: once any element is found, we can follow the connections and add the appropriate connections to our Abstract Syntax Graph.
Most languages that use graphs to represent data or a program do not use a 2D textual representations. Instead, they will provide IDEs that represent render the structure as a graph, but store it as a more easily processed form. Likely, the connections would be stored by IDs rather than by spatial locations, although the layout would be part of the stored information. LabView is probably one of the best-known visual programming languages that use graphs to represent control/data flow, but do not offer a textual representation of the program.
It is just dataflow: only the visual representation displayed to the user is 2D. Internally, this is a graph structure with a list of nodes and a list of vertices.
Look at VHDL, Verilog or any hardware description language for text-based dataflow languages.
Look at Excel or any spreadsheet for another representation of dataflow language.
The main difference is not in parsing, it is in runtime.
EDIT
The Funciton language actually is very specific in that source code is sort of ASCII art of boxes and edges. The first commit of the interpreter gives the general algorithm used for parsing that ASCII art:
- Find boxes and their outgoing edges
- Start finding a box here if this is a top-left corner of a box
- Find width of box by walking along top edge
- Find height of box by walking along left edge
- Verify the bottom edge
- Verify the right edge
- ...
- Parse the connections between nodes and discover all the loose ends ...
-
I can't see how does this answer my question. I'm just trying to understand how does a Lexer/Parser is designed for such a language where the source-code isn't just a usual C, Lisp or XML like source-code.– 53777AMay 14, 2014 at 7:47
-
@53777A Only the visual representation displayed to the user is 2D. Internally, this is a graph structure with a list of nodes and a list of vertices. May 14, 2014 at 7:58
-
1But in case of
Function
it seems that the source-code is both written and represented totally in 2D. At least as far as I have understood.– 53777AMay 14, 2014 at 8:05 -
Is the source code really typed in glyph by glyph with Unicode box-drawing characters? Or does the user open a special editor and insert elements via menus and shortcuts? In the latter case, the source code isn't really stored as a pseudo-graphic, it's just presented that way. Generating such a representation is much easier than parsing it. It appears the compiler is open-source, so if no one here knows, you can always take a look at the implementation to find out. May 14, 2014 at 8:23
-
1@53777A- You are correct: Funciton source code is sort of ASCII art of boxes and edges. The first commit of the interpreter gives the general algorithm used for parsing that ASCII art. May 14, 2014 at 9:05