Hi!
Yuri wrote:
Then for basic parsing I've generally written a recursive decent parser. However, given the limited stack of a 6502 I'm contemplating if a shift-reduce parser might be easier to work with memory management wise. (Though considerably harder to write)
The FastBasic compiler uses a recursive-descent parser, but implemented as a PEG parser, so each character in the input is one token and it does not need a lexer. This makes the parser faster, and it uses less memory as you don't need to store the input tokens as you parse the source directly.
In FastBasic, each parser call uses 2 bytes of stack for the return address and 2 bytes for the parsing state (the input and output pointers), as it parses lines of up to 255 bytes generating up to 255 bytes of code maximum. With this constraints, it is very difficult to find sequences that overflow the stack, this is an example from the test-suite that gives an error, because the parser calls itself after each ','
Code:
data y()=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,
53,54,55
Limiting stack usage also keeps the parsing fast, as you avoid the worst exponential behaviours.
To make the parser code smaller, the constructs are not written directly in assembler, the full PEG parser is stored as a state machine that is interpreted by the 6502 parser.
Have Fun!
Login
Register
FAQ
Search
)
