|
Usually Generalized parsing algorithms are complicated to implement due to being non-deterministic, but very powerful in that they can parse ambiguous grammars.
I really like GLR parsing because it's an elegant solution to a very complicated problem. It uses a difficult to implement LR parsing mechanism underneath but the G part of it is a relatively simple addition that supercharges the expressive power of the LR parser underneath and allows it to parse ambiguous grammars, like human language.
So when I wrote the Glory GLR parser generator I basically jumped the shark. There's little need for something more expressive as it already accepts any grammar. The only way I can think to improve on the algorithm is to implement a contextful grammar, but there are practical problems with even attempting this.
On contextful parsing
Context-sensitive grammar - Wikipedia[^] - it's not exactly a mathematically solved problem - at least not for every day parsing. The problem is that a computer is a Linear Bounded Automata and those aren't powerful enough to compute every CSG you can throw at it in practical time, but rather only a subset of them can be computed.
Recursively Enumerable Languages like English just aren't practically parsable using traditional means.
My prediction is that a learning system will be how we can parse such languages. We'd use machine learning to apply contextful meaning instead of taking a classic mathematical approach to break down the language linguistically and formally to a machine. At best, we'll partially parse using context-free means, like with GLR, and then work on each of the multiple trees we get back using some form of ML, essentially using context-free parsing to get our basic structures and then applying context using ML.
I believe that latter approach is already taken by some "AI" bot systems out there, like that ill fated microsoft twitter bot that turned into a Nazi. I can't be sure without looking at the code though.
Either way, it's a challenging problem. I'm not sure I'm up for solving it on my own. I don't even have the hardware I'd need to try it for anything real world, nor the man hours and expertise to produce a usable English grammar.
Real programmers use butterflies
|
|
|
|
|
well there is of course a long history of trying to parse natural languages, and
a variety of extensions to CFG's to handle that, usually in the form of attributing
grammars in whatever form. One form would be to add predicates to the grammar
where the predicate is used to select the direction of the parse (this is basically
why one prefers a handwritten recursive descent parser, since you can mix predicates
with symbol recognizers)
You might want to have a look at 2VW grammars (2 level van Wijngaarden grammars),
they were used in the description of Algol 68.
They are not "just" attribute grammars, since in most of the common attribute grammar
description the parsetree is annotated and the
attribute grammar is constrained such that in a finite - and preferably precomputed -
number of passes the attributes can be computed.
2VW grammars do contain (kind of) predicates that allow (or forbid) certain derivations.
Sine you seem to like exotic parsing techniques, handling some form of generalized
attributes during the building of the parsetree seems an exercise to keep you busy for
a couple of {weeks | Months | years} (select one)
|
|
|
|
|
I allowed for some measure of attributed grammars that could direct the parse in Parsley, but I've not found a practical way to implement 2 level van Wijngaard grammars (with all rewriting involved). And while they were probably used in the description of Algol 68 I bet it was human hands that implemented that grammar. That's my problem, is I'd want to cut out the human step. The GLR parser simply returns multiple trees for the different contexts and it's up to the consumer of those trees to select the right tree (and consequently applying context) - that's another route to go rather than 2VW, but 2VW does appeal to me in that it maintains formality and so it's I think possible, if not realistic to compute parsers for those grammars. However, they'd be slow.
Real programmers use butterflies
|
|
|
|
|
Indeed the A68 description was person-made, not mechanically.
It would be interesting though to see with what degree of constraints it would
be possible to handle it mechanically.
The most simple variant is of course an underlying LL(1) grammar with
predicates (or general functions) between symbols in the rules, predicates
that solely depend on the left context.
However, as soon as you are able - what you are - to generate a multitude of parse trees
you can evaluate constraints in a later stage and delete the trees where the
predicate results are false. The question is of course not whether or not it is theoretically
possible but whether or not you can formulate (levels of) constraints to make it practical.
For AG's is is pretty well known how to limit them such that the attributes can be computed
is a given number of scans over the tree, so given a finite amount of trees and a finite
amount of scans per tree to see whether or not the tree is viable, extracting the valid tree is - in principle - solvable. Assuming in natural language processing the basic elements to
parse and interpret are sentences, that should not give to many problems.
I do not know much about natural language processing, I do know though that most sentences
can be parsed in (many) different ways depending on the context. Context here in a very broad sense! (Due to sloppiness by most speakers the sentences spoken are inherently ambiguous
and require knowledge of the background of the speaker to be able to extract the precise intention of the spoken words.)
My examples would be in Dutch, so probably not very meaningful to you
Anyway, good luck with you parser (parsing) development, although I am not very active in that field anymore, I'll keep an eye on your progress
I
|
|
|
|
|
Member 12982558 wrote: However, as soon as you are able - what you are - to generate a multitude of parse trees
you can evaluate constraints in a later stage and delete the trees where the
predicate results are false.
GLR parsing allows for precisely that, but the trick is determining which tree to use. 
As I understand it, parsing using 2VW is generally polynomial time complexity. I'm not sure how that bakes out in the real world as I haven't implemented 2VW but my initial thought is it's probably impractical for large, real world grammars. I am sure that the grammar size is related to the performance, given how it works.
Real programmers use butterflies
|
|
|
|
|
“Quote: Abusive treatment given to plant base (11)
Answer is molestation.
As nobody has played the past couple of days I’ll leave one of you to add the solution.
|
|
|
|
|
Pompey 3 wrote: Abusive treatment given to plant base (11)
Plant base = Station?
Treatement given to = Mole???
cheers,
Super
------------------------------------------
Too much of good is bad,mix some evil in it
|
|
|
|
|
Abusive treatment - molestation
Plant - mole as in spy
Base - station
Thinking I’m overthinking them then?
Easy one tomorrow
|
|
|
|
|
Pompey 3 wrote: Thinking I’m overthinking them then?
Definitely.
|
|
|
|
|
^If the right-pond people are complaining, you can imagine how the rest of us feel.
Let's just say fair but cruel. If you can get past plant base = stalk, stem, root... you have a chance, though getting from plant to mole is tough.
If you're ever finished with software, send some of them to British newspapers. 
|
|
|
|
|
No we don't want them - I'm with you I was thinking stem,stalk etc... would never have thought ( nor have I ever come across mole as plant ) of mole
"We can't stop here - this is bat country" - Hunter S Thompson - RIP
|
|
|
|
|
Well that was the point to throw you. Do you not remember DDs hard ones?
Oh has turned you all into welsh sissy’s
|
|
|
|
|
SPACEX - ISS Docking Simulator[^]
See if you can spot the easter egg...
One morning I shot an elephant in my pajamas. How he got in my pajamas, I don't know.
|
|
|
|
|
Is it the round chocolate thing wrapped in cheap foil?
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
|
mostly because it was bass-ackward.
tapping say the left side/arrow should mean fire the left thruster (which would spin you right)
not fire the right thruster to spin left.
1. your eye needs to remain on the target, not where your sight is pointing
2. your POV becomes relative from the target to you
3. you then nudge your sight to the target
#2 having effectively reversed your POV (basic human wiring) tells your brain: push on the left side to make my sight move to the right.
ask any sniper -
1. never take your eye off the target
2. your sight/crosshair is attached to you, (i.e. the end of your barrel), your muscles always know where it is.
... need to move to right: push with your left arm, (never pull with the opposite arm)
pestilence [ pes-tl-uh ns ] noun
1. a deadly or virulent epidemic disease. especially bubonic plague.
2. something that is considered harmful, destructive, or evil.
Synonyms: pest, plague, CCP
|
|
|
|
|
Abusive treatment given to plant base (11)
|
|
|
|
|
Only skill enhanced during lockdown was cooking various international cuisines. But I have major issue with 3 things. All website and chef must standardize the cooking parameters
1. Prep time : doesn't include the time to peel off, clean/cut various vegetable etc . 15 mins prep time means 45 for me 
2. Meal for 2 or 4: It is so misleading. Either I end up cooking for one person or for the whole village and then some.
3. At the end of all cooking vblog, Please show how your kitchen looked like and then it what is the outcome.
cheers,
Super
------------------------------------------
Too much of good is bad,mix some evil in it
|
|
|
|
|
|
'Fond' memories of cooking a rice based dish, 'thats not enough, I'll add some more' I could have fed mainland China for a week with the results! 
|
|
|
|
|
I did something similar when cooking stew and dumplings, I thought the amount of dumplings I got from the recipe seemed a little on the small side ( I do like my dumplings) so I tripled the dumpling mix.
Big big mistake and it got bigger the longer it cooked.
I try and follow the recipe now rather than making up the proportions on the fly.
|
|
|
|
|
I know, I think the people who write the recipe might have that sort of experience!
|
|
|
|
|
Tony Hill wrote: proportions on the fly.
Nowadays , my ingredients are on the fly. "This is not there, no problem Ill replace with this."
cheers,
Super
------------------------------------------
Too much of good is bad,mix some evil in it
|
|
|
|
|
Through university and graduate school, most of my friends were Chinese. Amongst my post important cooking lessons (given indirectly, except eggroll were taught) I learned the most important rule about cooking and ingredients:
What are the ingredients needed for your dish? : Whatever you have on hand, those are them.
This also goes to what you do when you go shopping - local vegetables - no need for anything rare and exotic. It always works out.
| 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 seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
glennPattonWork wrote: 'thats not enough, I'll add some more'
My nemesis.
cheers,
Super
------------------------------------------
Too much of good is bad,mix some evil in it
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
