4 ms·
From what I understand, the idea is you have some string S and an input T, and running a grammar G on ST will produce an output. Sometimes they won't halt. Just
by aleeds 10y ago
From what I understand, the idea is you have some string S and an input T, and running a grammar G on ST will produce an output. Sometimes they won't halt. Just like a Turing machine.
In this analogy G is the 'universal Turing machine'
- zingermc 10y agoInteresting! I think I am starting to get it. To double check, is running a grammar the same as parsing?
- thesz 10y agoThe two-level grammars are doing things in two steps: parsing of part of the text yields a grammar for parsing the rest of it. The Algol-68 was specified using two level grammar and if I understand it correctly, the declaration part constrained parsing of the statement part so that only valid expressions can be parsed. Parsed statements are valid in the semantic sense, i.e., the subscription can be applied only to array values and parser will reject subscription for scalar values. To generate the grammar you need to execute some function. And this function depends on the part of input.
- zingermc 10y agoWow, the two-level grammar concept is incredible! I have some learning to do. Thank you for sharing.