3 ms·
Learn what lexing is. That's step one. Once you have a token stream, look into how you'd transform them into structures. PUB FN ID(main) OPAREN CPAREN COLON ID
by junon 5y ago
Learn what lexing is. That's step one. Once you have a token stream, look into how you'd transform them into structures.
PUB FN ID(main) OPAREN CPAREN COLON ID(i32) OBRACE NL RETURN NUMBER(0) CBRACE
Look familiar? How might you parse that into something like
{
kind: "function",
name: "main",
args: [],
public: true,
return_type: {
kind: "integer_type",
width: 32
},
body: [
{
kind: "return",
expression: {
kind: "number_literal",
value: 0
}
}
]
}
A recursive descent parser is just a parser that starts at a root node type and recursively traverses a token stream and calls handler functions based on what's next. Those functions might also call other handlers (e.g. for nested expression parsing, etc.) which is why it's called recursive.
- mbrodersen 5y agoActually don’t. Knowing how to write parsers without a lexer (scanner less parsers) is the true superpower.
- junon 5y agoFully disagree. Care to expand?
- mbrodersen 5y agoScanner less parsers are strictly more powerful than parsers using fixed lexers. You can literally change the language you are parsing based on what you have parsed so far. I have code running in production doing exactly that.
- mbrodersen 5y agoDownvoting without giving a reason why is not useful.
- junon 5y agoGenerally such languages are so abstract that they lose usefulness in practice. Because something can be done, doesn't mean it should. Writing a simple recursive descent parser with a Lexer's token stream is much easier than doing bytestream ingestion on the fly, especially for a beginner.
- mbrodersen 5y agoYou can even parse a definition of a parser and then continue parsing the rest of the code using that parser. Not something I have needed in production but it shows the power of non-lexing parsers.