On Thu, Mar 01, 2018 at 07:28:49AM +0100, Julia Lawall wrote:
>
>
> On Thu, 1 Mar 2018, David Gibson wrote:
>
> > On Wed, Feb 28, 2018 at 07:39:35AM +0100, Julia Lawall wrote:
> > >
> > >
> > > On Wed, 28 Feb 2018, David Gibson wrote:
> > >
> > > > On Mon, Feb 26, 2018 at 08:33:06AM +0100, Julia Lawall wrote:
> > > > >
> > > > >
> > > > > On Sun, 25 Feb 2018, frowand.list@xxxxxxxxx wrote:
> > > > >
> > > > > > From: Frank Rowand <frowand.list@xxxxxxxxx>
> > > > > >
> > > > > > Hi All,
> > > > > >
> > > > > > I am once again out of my depth with bison and flex.
> > > > > >
> > > > > > The Devicetree Specification and ePAPR both tell me that I can
> > > > > > put a label on a node, as in:
> > > > > >
> > > > > > [label:] node-name[@unit-address] {
> > > > > > [properties definitions]
> > > > > > [child nodes]
> > > > > > }
> > > > > >
> > > > > > and do not make any mention of the root node as being different
> > > > > > that any other node in this respect.
> > > > > >
> > > > > > However, the dtc implementation does not allow a label on the
> > > > > > root node. I tried modifying the dtc parser to allow a label
> > > > > > on the root node. The result is patch 1/2 in this series.
> > > > > >
> > > > > > After applying patch 1/2, I get a syntax error when I try to
> > > > > > compile a devicetree source with a label on the root node:
> > > > > >
> > > > > > $ dtc -O dts junk_lab.dts >junk
> > > > > > Error: junk_lab.dts:3.9-10 syntax error
> > > > > > FATAL ERROR: Unable to parse input tree
> > > > > >
> > > > > > Here are the first few lines of the source file:
> > > > > >
> > > > > > $ nl -ba junk_lab.dts | head
> > > > > > 1 /dts-v1/;
> > > > > > 2
> > > > > > 3 myroot: / {
> > > > > > 4 #address-cells = <0x1>;
> > > > > > 5 #size-cells = <0x1>;
> > > > > > 6 compatible = "qcom,apq8074-dragonboard", "qcom,apq8074";
> > > > > > 7 interrupt-parent = <0x1>;
> > > > > > 8 model = "Qualcomm APQ8074 Dragonboard";
> > > > > > 9
> > > > > > 10 adsp-pil {
> > > > > >
> > > > > > I did my best to debug the cause of the symptom, and at one point
> > > > > > tried removing the parse code that allows /memreserve/ to have
> > > > > > a label, which is patch 2/2. This was just trying to better
> > > > > > understand what was going on, not actually with the intent of
> > > > > > submitting patch 2/2 for real. However, I can successfully
> > > > > > compile a devicetree with a label on the root node when I
> > > > > > have both patch 1/2 and patch 2/2 applied.
> > > > > >
> > > > > > Am I missing something that will let me add labels to the root
> > > > > > node _without_ having to remove the capability of having
> > > > > > labels on /memreserve/?
> > > > >
> > > > > OK, I read the mails out of order, so I see that you found the memreserve
> > > > > problem. Is there a way that you expect the grammar to know whether the
> > > > > label is part of the memreserve declaration or the devicetree declaration?
> > > > > It needs to know immediately so it can choose between the rules
> > > > > (memreserves and devicetree).
> > > > >
> > > > > Is it intentional that memreserve is recursive? Ie that lots of labels
> > > > > should be allowed before a given DT_MEMRESERVE? If it were not recursive,
> > > > > it might be smart enough to realize that the two kinds of DT_LABEL are
> > > > > followed by different things.
> > > >
> > > > Yes, that's intentional. In general if something allows one label it
> > > > should allow an arbitrary number.
> > >
> > > OK, so then maybe the grammar can be refactored to match lots of labels
> > > and then some rule that will contain some explicit tokens to help it
> > > figure out when to figure out to switch from the memreserve state to the
> > > device tree state.
> >
> > I think that'll work from a grammar point of view. From a parser
> > semantics point of view, I suspect it will be a bit of a pain,
> > requiring passing the label information about in an awkward way.
>
> That's what LR parsing is all about...
Kinda, yeah.
> But if bison has a more intelligent strategy, then certainly go for
> that.
I believe the %glr-parser option uses a GLR / Tomita algorithm parser
(https://en.wikipedia.org/wiki/GLR_parser).
It basically operates like an LR parser engine, but when there's a
conflict it dupes the parser state and follows all possible paths
until they either die out in syntax errors or reconverge on each
other.
In theory it's O(n^3), but in practice the n^3 bit only applies for
the duration that it has to go into that split operation, which is
generally only a handful of tokens so it performs well in practice.
So, I'm not really concerned about the performance, but I am at least
slightly concerned about people who might have an old Bison version
which doesn't support the option.
--
David Gibson | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_
| _way_ _around_!
http://www.ozlabs.org/~dgibson
Attachment:
signature.asc
Description: PGP signature
