From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: border1.nntp.dca1.giganews.com!nntp.giganews.com!news.glorb.com!peer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!post02.iad.highwinds-media.com!news.flashnewsgroups.com-b7.4zTQh5tI3A!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: [Slightly OT] How to process lightweight text markup languages? References: Date: Fri, 23 Jan 2015 04:24:51 -0600 Message-ID: <85h9vh94lo.fsf@stephe-leake.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (windows-nt) Cancel-Lock: sha1:RahTSoDEq9uc2RF2/HOnebKTyw8= MIME-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@flashnewsgroups.com Organization: FlashNewsgroups.com X-Trace: ad6f554c2217fe3fb833031236 X-Received-Bytes: 2177 X-Received-Body-CRC: 2667313445 Xref: number.nntp.giganews.com comp.lang.ada:192023 Date: 2015-01-23T04:24:51-06:00 List-Id: Natasha Kerensikova writes: > This led me to the conclusion that the only solutions are backtracking > and simultaneously parsing all available possibilities (i.e. using a > nondeterministic automaton). Considering the current state of computing, > I should probably go for backtracking. I don't follow; why is backtracking better than parallel parsing? They both search the same tree of possible grammar sentences; it's just depth-first vs breadth-first search. > Basic backtracking would be pushing the current state when encountering > an opening marker, and if the end is reached with a non-empty stack, pop > the top-most state, replace the opening marker by the literal > sequence of its representation, and restart parsing. Right. In parallel parsing, you don't wait for the first one to fail; you just assume it will. > If I'm not mistaken, adding precedences to the mix would just change the > meaning of "end is reached" in the previous paragraph: it would not only > mean the end of input, but also the ending marker of any > higher-precedence construct currently in the stack. Sounds right. > Am I right so far? Am I missing something? You are only missing an implemention of a parallel parser and lexer. There is an example of the first in OpenToken; the second should not be hard. -- -- Stephe