|
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!
|
|
|
|
|
|
|
|
Azure is not really something you learn, but a bunch of services/hardware that you rent from MS. I've been using Azure services since 2015 to host lob web apps for multiple clients. You may think that it's the same as a webhost but the difference is that the resources you are renting are scalable, both up and out.
One type of Azure service that I am using is a Server 2016 VM hosting multiple customer lob web applications. In the beginning, we rented a total of 4 webapp (.Net btw) slots and 2 sql databases for <$100 a month. When we needed to add more apps, the decision was made to get another domain name and tie it to an Azure VM. It's handling half a dozen customer web apps nicely, and can likely double capacity before I even think about moving up a tier. It's super nice when I need to troubleshoot something for a customer...just rdc in and fix the problem.
They used to give you a 30 day free trial. One word of advice if you decide you need anything Azure...check out the deep discounts you get for annual reservations.
"Go forth into the source" - Neal Morse
"Hope is contagious"
|
|
|
|
|
Thanks for the info. It's interesting you mention hosting because I'm going to be setting up a Web API for an app I'm working on for a client. I was just going to host it in IIS on their server. How/why would using Azure be better?
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
