|
I can, but it's involved. You have to do it in steps, and it depends on what kind of parser you're generating.
The main thing though, after you understand the fundamentals, is generating "first" and "follows" sets which are basically what they sound like - they tell you the first symbol from a production, and they tell you what can follow a production**
** vocab will take a minute. How much time you have?
I first have to start by explaining what a Context-Free Grammar is and how the data for one is laid out.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
codewitch honey crisis wrote: vocab will take a minute. How much time you have?
I make time for anyone who can teach me.
Consider time yours.
codewitch honey crisis wrote: I first have to start by explaining what a Context-Free Grammar is and how the data for one is laid out.
Yup, all blank on that subject.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Okay, so parsers work generally using a method called substitution.
I'll show you. A context free grammar is a mathematical entity. It is a type-2 language on the Chomsky scale (if your ever interested in what all that means - yours to google later, but it's not necessary here)
so here's a CFG - it's a series of rules. And a start symbol. I'll explain.
A rule takes the form of (example)
binop → num + num
- in this case marking a binary expression as "num + num" (two numbers with a + inbetween them - num is defined elsewhere as a regular expression matching a series of digits)
follow so far?
obviously that doesn't represent much of a binary expression. We need to do more than add!
let's define more rules
binop → num - num
binop → num * num
binop → num / num
that's more like it!. Now you may notice that there's the same left hand side on each of those.
A group of rules with all the same left hand side are called collectively a "non-terminal"
here, binop is a nonterminal. num is not but we'll get into that
Nonterminals can have rules that can reference terminals or other non-terminals, and even themselves recursively
A CFG tells us what the rules are, and just as importantly, which non-terminal to start at (here it would obv be binop since we haven't) declared any others.
Follow so far?
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
modified 7-May-19 16:06pm.
|
|
|
|
|
codewitch honey crisis wrote: Follow so far?
Kind of. When talking parsers, I think of a "simple" interpreter-pattern.
How would you enforce the rules you declare?
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
The parser does that during the parse process. It's pretty straightforward. Basically consider an LL1 parse table as a table of dictionaries nested in another dictionary. If you can't index into each dictionary successfully based on the current stack and state then it's a parse error. We'll be generating that table from the CFG (context free grammar)
in terms of building the table, i usually validate the grammar before i begin with a Validate method.
i'll keep going as far as explaining in a separate reply but i just woke up and i need some coffee
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
alright, after reading my other reply, and asking any other questions you have, let's continue:
recall our grammar
binop → num + num
| num - num
| num * num
| num / num
We won't be using this one. There's no operator precedence in it. and no parenthesis
Expr = Expr '[\+\-]' Term | Term
Term = Term '[/\*] Factor | Factor
Factor = '\(' Expr '\)' | int
int = '[0-9]+'
Woah. This is more practical but
a) it's not a straight CFG
b) it looks messy and confusing
Let's take care of that.
First, all the single quoted strings are regular expressions
those are our "terminals" - they represent the leaves of the parse tree will be parsing.
CFGs care about terminals, but NOT their definitions.
Let's rewrite this to be purely a CFG - we'll separate the terminal definitions out and leave them aside:
Expr = Expr add Term | Term
Term = Term mul Factor | Factor
Factor = lparen Expr rparen | int
There we go. All the terminals are lowercase, and the non-terminals are title case (not required, just a convention we'll use here). The definitions of the terminals are gone, replaced by labels.
How can a CFG tell what's a terminal and a nonterminal just from this? simple - a non-terminal is anything that appears on the left hand side
Anyway, next we will break out this | (or) expressions into separate rules
Expr → Expr add Term
Expr → Term
Term → Term mul Factor
Term → Factor
Factor → lparen Expr rparen
Factor → int
This is how a CFG likes it. Whew. One more major step, and it's a little involved.
The last issue here is that this is left recursive. The rules reference their left non-terminal on the leftmost part of the right hand side. Some parser algorithms (the LR family is an example) can handle this but an LL can't - it would loop infinitely.
So now we have to refactor this CFG. It can be done programmatically. (My code does this)
Let's take a look at the first two rules
Expr → Expr add Term
Expr → Term
For each rule where the non-terminal on the left (Expr) of the arrow is the same as the left-side of a production on the right-hand side of the arrow (Expr add Term), we take the part of the rule without the recursive bit (which leaves us with "add Term") and move it down into its own new rule (we'll call it Expr').
Expr' → add Term
Now, after each of the new productions, add Expr' to the end.
Expr' → add Term Expr'
Still not done. Now add an extra rule with an ε (epsilon) which just means an "empty string" - matches without consuming or examining input.
Expr' → ε
Good. Now we must fix up the original Expr rules. Here, we take all of the right-hand sides that didn't start with Expr, and add Expr' to the end of them.
Expr → Term Expr'
If we do this for the Term productions as well, we get the following grammar:
Expr → Term Expr'
Expr' → add Term Expr'
Expr' → ε
Term → Factor Term'
Term' → mul Factor Term'
Term' → ε
Factor → lparen Expr rparen
Factor → int
TADA!, and we're done so far. I'll take this opportunity to stop and wait if you have questions.
I've covered a lot here so far. Some of this was ripped from this wonderful LL(1) tutorial
So once you respond and check in, we'll keep going.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
codewitch honey crisis wrote: TADA!, and we're done so far. I'll take this opportunity to stop and wait if you have questions.
No questions, but I'll have to read this again tomorrow.
It's quite the chunk of information, and I'm currently a bit.. slow 
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
cool. just reply after you've had a chance to digest it tomorrow or whenever. =)
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
I read it three times now, and get the feeling this is a very short introduction. Did I read it correct that you are writing a longer article on the subject?
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
I'll be submitting some code, along with an introduction to the subject. I'm not sure how much ground I will cover there though. This stuff, even LL(1) parsing, is involved. LL(1) parsing isn't even that complicated - it's just involved.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
codewitch honey crisis wrote: I'll be submitting some code, along with an introduction to the subject. I'm not sure how much ground I will cover there though.
Intro is enough; it doesn't have to be a complete book on the subject 
If that's read often, you'll get enough requests for a followup and part 2
codewitch honey crisis wrote: This stuff, even LL(1) parsing, is involved. LL(1) parsing isn't even that complicated - it's just involved.
That goes even for a blockchain, but that doesn't mean that everyone has one. Once you know how stuff works, it becomes obvious.
Currently learning to live without painkillers, so my attention-span is rather limited. There's a lot more people looking at the article-submission queue, so you'll have a good test-audience (and hidden peer-comments) before going live with the article.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Not really an intro to the topic, but some code, and an explanation of the algorithm I used to increase the parser's expressive power.
Newt: A Powerful C# Parser Generator in a Small Package[^]
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
codewitch honey crisis wrote: Not really an intro to the topic, but some code, and an explanation of the algorithm I used to increase the parser's expressive power.
Newt: A Powerful C# Parser Generator in a Small Package[^]
Nice 
Not very familiar with parser generators, but looks like I may want to change that.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
The three best breakfast foods, in order of precedence:
0. Trifle
1. Cold lasagna with ketchup
2. Leftover curry
Although the missus swears by by signature melted cheese + fried-and-shattered prosciutto + fried egg + fresh spinach + peanut butter + Tabasco sauce sandwiches -- or, when mushrooms are in season, my magnificent mushrooms on toast (recipe not exactly stolen, but I can't remember where I got it from, so I can't attribute it).
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
codewitch honey crisis wrote: Do you get weird code related food cravings
No! I learned many years ago not to code when I'm stoned.
Never underestimate the power of human stupidity -
RAH
I'm old. I know stuff - JSOP
|
|
|
|
|
lol
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
|
I'm told the cake is a lie
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
|
with their latest debacle last straw that has me finally sh*t-canning firefox.
but there's things that I liked in ff that chrome and others (played with opera yesterday too) just don't do, or don't do right.
getting desparate... perhaps a firefox branch???
well: I'm on Pale Moon and loving it.
OK not so many extensions available (but got the important stuff like ad-blocker).
"Expert" reviews said it's firefox a few versions ago...
(and ** warning warning, it's behind in security patches, up to 9 days behind! warning warning **.)
well my finding: it's not "firefox a few versions back." well OK it sort-of is, but it isn't, not by a mile.
there's none of the mozilla.org crap (pocket, removing features such as asking to save on exit, and all the "mozilla thinks you're to stupid so we removed it" preferences are there... way way way less mozilla sh*t and stupidity
it's actually firefox done properly: ff for the users, not the marketing dept (which apparently is what's killing moz)
"9 days behind on security patches" - OFFS, please, 99.999% of 'security patches' are obscure tiny crap that only happens if you go to obscure crap websites and do something that anyone with more than half a brain cell wouldn't do regardless of where you're at, (stupid is...)
OIOW: FARK OFF "EXPERTS" fark off and while you're farked off how about wiping down all them certificates that your wanking reviews and in-your-dreams useful advice ex-spurted all over.
oh and the other good thing about pale moon: it's not goggle chrome (aka the new "internet explorer")
Message Signature
(Click to edit ->)
|
|
|
|
|
Chrome is the only browser I use personally.
Um, I guess give FF a bit of time to get their act together, etc. and then try them again? I would not write them off completely. Have they not been a great browser over the years for the most part? your post is too long and I am to lazy to read the whole book. 
|
|
|
|
|
I am curious what was that debacle? I got fed-up with FF. I like the Vivaldi browser, and occasionally go Chrome.
"If we don't change direction, we'll end up where we're going"
|
|
|
|
|
basically some certificate screw up that cause every add-on to be disabled .. EVERY add-on, not just some, every single add-on. 1 day later they suggested a temporary work-around that worked for maybe 25% of the users, few days on they've supposedly released an update but even then they admitted it was incomplete and would only help some people.
have you tried running your browser without adblock (or whatver blocker you use)? and all those other extensions/add-ons you don't even think about anymore, even the simple ones.
not fun at all,
Message Signature
(Click to edit ->)
|
|
|
|
|
It's been fixed now. All add-ons work.
|
|
|
|
|
I have an old version of FireFox running because it no longer supports some of the add-ons I like (like FireFTP).
Today - and I mean during the day - somehow they updated my FireFox (same old version) and it no longer will run my Adblocker or web-beacon handler. Just like that.
Interestingly, they are now allowing trash into my system that invades my privacy, like the web beacons because the think that 'unsigned' add-ons might violate my privacy by transmitting information.
Especially doing this without a word or warning or permission, they crossed the line.
Morons.
| Ravings en masse^ |
|---|
| "The difference between genius and stupidity is that genius has its limits." - Albert Einstein | | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
