search

kjosib / booze-tools

Booze Tools will become the complete programming-language development workbench, all written in Python 3.9 (for now).
MIT License
14 stars 1 forks source link

Tainting = PGM? #47

Closed modulovalue closed 7 months ago

modulovalue commented 10 months ago

Hey @kjosib,

I've been reading your minimal doc and Xin Chen's dissertation on various LR(1) construction algorithms. His explanation of Pager's lane tracing reminds me a lot of your approach. I'm wondering, are you aware of Pager's work and if so, can you comment on how your approach differs from his?

(In particular, starting from Page 72, Phase 2, Pager's lane head list, as described by Xin Chen, appears to be similar to your tainted head parse items, and Pager's states where PASS_THRU=on appear to be similar to your tainted states.)

modulovalue commented 7 months ago

I'm closing this as stale.

kjosib commented 7 months ago

Must have missed the notifications. Anyway yes I'm vaguely familiar with Pager's algorithm. Back in the day I ran through a whole bunch of material with more concern for understanding than attribution, so I can't really give an academic bibliography for this code. The biggest influence on the Minimal-LR(1) ideas in this code is undoubtedly the IELR paper, which has the advantage of working in conjunction with precedence and associativity rules. I'm sure there's some cribbed from everything I could find. I was not looking to re-implement lane tracing exactly; more to try to find a way to get the job done that was easier (for me) to understand. I would not be surprised if there was a close parallel or bimorphism between the approaches, but that was never a goal -- unless it should turn out that all workable methods are fundamentally the same under the hood.

modulovalue commented 7 months ago

I see, thank you for the comment @kjosib