|
When I was in the Navy, we had a record player in the shop. Someone had the "Days of Future Passed" (?) album, and in a 12 hour shift, it got played 6 times, at least.
Not to be trollish about it, but, the overexposure made me come to HATE the Moody Blues. "Nights in White Satin" particularly. To this day, whenever they come on the radio, I imediately find another channel.
I am sorry to see anyone die, and that certaily applies to Graeme Edge. All of his problems are over. It is the fans left behind that suffer the loss.
|
|
|
|
|
Earlier I said I had trouble understanding the family of bottom up parse table building algorithms.
I don't want to claim I suddenly know it all but I just figured out something that I think ANTLR did based off of it.
Regular Expression engines work by matching characters in text using state machines.
These bottom up parsers work by matching tokens rules (like Foobar -> "bar" "baz") and tokens that it gathers into a stack. I crossed out tokens because that's how i sort of figured it worked before.
Anyway, I don't really care that I understand say, LALR table building a bit better now. But regarding ANTLR, the gentleman who invented it used state machines to recognize and match possible dysjunctions for LL(k) parsing in an incoming token rule stream. Like when a grammar is ambiguous where k=1 but not where k=3 the difference can be made up using recognizer state machines for the additional lookahead. These would be built in a very similar way as my existing code that builds LR(1) parsers.
LL(k) has always been an elusive beast for me where k>1. I don't understand the math, nor did I get the concepts as they were presented to me.
But perhaps I have something here, after all this time now.
If I can get to LL(k) it opens up the possibility of being able to write grammars to parse languages like C# without resorting to custom parsing code for parts of the grammar, or resorting to GLR which is awful to use in practice.
Anyway, woo! I have so much work in front of me now between upcoming CP contributions and actual work that I won't be able to get to this for a bit, but it gives me time for it to sort of crystalize in my head before I start writing code.
Real programmers use butterflies
|
|
|
|
|
Can you please also give a simple introduction to the subject - for single-celled organisms like me?
Or do you think we all here are somehow connected to your thoughts / activities in a magical way?
Thanks  
|
|
|
|
|
Sorry, it's a result of trying to keep my post brief and compress a lot of information into a little space.
Tokenizing, or lexing text uses state machines to run regular expressions over an input text stream. It marks "lexemes" in text like IntegerLiteral or Keyword or StringLiteral. In the end it tags all text with a symbol id indicating what it is (keyword, int literal, or whatever) - these are returned as a series (stream) of tokens.
These tokens are used by parsers, which use a special kind of state machine that drives a stack as well as an input cursor. The input cursor this time is over tokens instead of text.
Parsers to put it simply, impose a hierarchal structure over those stream of tokens, based on a grammar. This yields a parse tree.
Some parsers (the LL family of parsers) use leftmost derivation and therefore construct the trees from the top down, starting at the root node in the grammar and working toward the leaves by eating input tokens.
Some parsers (the LR family of parsers) use rightmost derivation and therefore construct the trees from the leaves to the root, matching a series of tokens (or previously reduced rules), and then replacing those with the rule that represents them until the root rule is reduced. Recursively you can create a tree with this as well.
LL(1) means LL parsing with 1 token of lookahead. LL(0) parsers are not practical as they can't match anything significant (but LR(0) can).
LL(2) is more difficult because the extra disjunctions causes an exponential growth of your parse tables. Think of it like the difference between the number of guesses you'd have to make to brute force a 1 vs 2 digit pin #. It's like that.
LL(k) means k is arbitrary and usually dictated by whatever the grammar demands.
I think I can achieve LL(k) by using some of the algorithm from my LR parser construction.
Real programmers use butterflies
|
|
|
|
|
To be honest: I say 95% here can't follow them and make a smile on their faces.
Now you have tried to explain it with LL (1), LL (2), LL (k), your area of expertise ... I claim once again that 95% here do not understand ...
This is your story that needs a lot of knowledge to understand and one need a lot of prior knowledge to understand your posts.
And of course there are always goofs who say yes to everything without understanding it.
Sorry 
PLEASE
Keep going with your articles and maybe do an article for beginners like 'parsing for noobs step-by-step' or something like a 'light weight' introduction for parsing.
All the best, you are great!
|
|
|
|
|
|
TIL. Well written and concise 
|
|
|
|
|
Yay! Someone understood my ravings!
Real programmers use butterflies
|
|
|
|
|
It seems like a lot of ideas from regular expressions carry over and I've done a lot of regex. I get why LL(0) wouldn't work but it's not immediately obvious why LR(0) does. I'll have to mull over that for a bit still 
|
|
|
|
|
They seem like they would be analogues but opposite, and yet they aren't. As a general rule, driving your decisions based on the input (LR) rather than the specification (LL) yields greater matching power.
Real programmers use butterflies
|
|
|
|
|
Adding, as far as carrying over from regex, that's true of LR, but not so much of LL.
They are all forms of automata, but with LL and regex that's where the similarity - in terms of the math of it - end.
The reason is that LL and LR match Chomsky class 2 languages while regex can only match class 3 languages.
It's the introduction of a hierarchy that creates the issue, and breaks so much of the math. For example, while two regular expressions can be converted to FA graphs and compared for equivalency the equivalency of two grammars (called context free grammars or CFGs) cannot be decided.
The reason LR shares some ideas with the regex/FA world is because of how it matches rules on the stack. It uses finite automata, like regex, to look for those patterns. But it uses those matches to create a hierarchy - each time a "reduce" happens, a new node (with a corresponding rule) with potential children is put in the tree. Regex has no such corollary. Its accepts however, are similar in this case, but they don't do anything to create parent child relationships, while "rules" themselves do.
An LR parser is a PDA (push down automaton) that uses FA (finite automaton) to help its PDA process. FA is where the regex similarities come in.
With LL (aside from certain implementations of LL(k)) there's not even a corollary there because no regex style matching is used. Instead it's entirely driven top down using a decision table and a stack. Yes, it's a state machine itself, but it works so much differently than a regex thing, there's no FA involved, just a PDA.
*hides*
Real programmers use butterflies
|
|
|
|
|
Ever thought about writing an article about the fundamental concepts of these topics like PDA, FA, etc? I've been doing some reading because I feel like I only partially understand this and I'm having an issue understanding this particular part:
honey the codewitch wrote: An LR parser is a PDA (push down automaton) that uses FA (finite automaton) to help its PDA process. FA is where the regex similarities come in.
With LL (aside from certain implementations of LL(k)) there's not even a corollary there because no regex style matching is used. Instead it's entirely driven top down using a decision table and a stack. Yes, it's a state machine itself, but it works so much differently than a regex thing, there's no FA involved, just a PDA.
From what I can gather, a PDA still has state transitions, so I'm at a bit of a loss here since state transitions seem to be basically what FAs are. I feel like I'm missing something important about the definition of state and/or state transitions that the articles I'm reading gloss over.
I really like the use of the term "reduce" when describing LR parsing btw. For me at least that really made your point about the difference between regex and LR parsing click in my head. At least I think it clicked 
EDIT: To be more clear, I'm confused as to why an LR parser is a PDA + FA but LL is just PDA. How can you have a PDA without FA, and what significance does that hold?
modified 12-Nov-21 23:06pm.
|
|
|
|
|
FA's are a restricted subset of a PDA mathematically, but practically speaking they are entirely a different animal. There are too many properties of them that are fundamentally different, including the fact that equivalency is undecidable for PDAs. Implementing FAs (meaning in this case, DFAs and NFAs) requires nothing more than an input stream. A PDA requires that and a stack. They both have transitions, but they operate on them differently.
Edit: What I mean is the LR parse tables are literally built through the creation of stackless FAs in addition to the PDA that drives the whole thing
Real programmers use butterflies
|
|
|
|
|
I am not sure this is exactly on point but I will still state I studied compiler design via the so called "Dragon" tome on the subject I can't say I still have a firm grasp of the difference between top down and bottom up parsing even though I worked all the problems but stopped at emitting code as I had no intention of writing a compiler but it was enough for me to utilize the code provided by Alan Holub in his text to fabricate a C expression parser and further enhance it by making it re-entrant as the pointer types utilized in the app I created pointed to objects w/ associated expressions of their own It was easier than expected However the final app created though first of its' kind was not a commercial success while some years later another is apparently successfully owning the market as it is the only one of its'/my kind though it has a glaring deficiency which mine does not Unfortunately Mr. Jerry Pournelle despite his stated interest in reviewing my software did not wish to download it as he stated his download speed was too slow though I insisted its' size was a mere 1MB He requested a CD copy but I had none and my machine in those days did not have a CD drive and I had little confidence in installing one A business man I am not - Cheerio
|
|
|
|
|
The Dragon Book has a way of making simple things complicated.
Basically, bottom up parsers work by deducing the next rule they need to match from the series of input tokens and previously matched rules they have on the stack.
Top down parsers work by deducing the next rule based on a decision table they run, and it expects the input tokens to match that table
The bottom line is that bottom up parsers primarily use the input tokens to drive their decision making process, using the grammar as a guide. Top down parser primarily use the the grammar to drive their decision making, using the input tokens as a guide.
The other difference is in the way they construct the tree as a result of this.
Bottom up parsers start at the leaves of the tree - the terminal tokens, and compile those into the next level rules, which it then compiles into the next level of rules (containing the rules it matched on the previous level before) and so on until it reaches the root of the tree. You will not get the root of the tree until *after* the entire document is parsed.
Top down parsers start at the root of the tree - the start non terminal in the grammar, and work their way toward the leaves - the terminals. They can yield the first node in the tree as soon as they start parsing - technically even before reading any input.
I find top down parsers to be superior to use, but bottom up parsers are more powerful generally speaking. LL(k) is as powerful as one needs it to be though, so if I can crack that, I can pretty much ignore bottom up parsing moving forward.
Real programmers use butterflies
|
|
|
|
|
Serious question. What is Azure and why should I care?
I'm asking because I see the term alot and I've yet to learn it. I'm solely a Windows developer and have done just fine for 35 years. So, do I need to learn Azure?
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
|
It's the colour between cyan and blue in the visible spectrum of light.
What, you weren't expecting a serious answer in The Lounge on a Friday afternoon, were you?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Richard Deeming wrote: It's the colour between cyan and blue in the visible spectrum of light.
How can it be serious when you spelled 'Color' as 'Colour'???
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
|
Look, just because Noah Webster preferred the Latin root "color" to the Norman word "colour", that doesn't make our (correct) spelling any less valid.
(Maybe we should avoid the argument altogether, and just use "hew" instead?)
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
You say Potato, I say Potato..... oh wait..
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
|
Richard Deeming wrote: "hew"
Not if you're going to cry about it.
:rim-shot:
Software Zen: delete this;
|
|
|
|
|
It's not my favourite way of spelling it, neighbour. Knowing how to apply grammar rules takes some labour, but I try to find some humour in it.
|
|
|
|
|
#008AD8[^]
You're welcome!
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
