preferred language/technique for sequence processing or parsing

Question

I have come across similar problems a few times in the past and want to know what language (methodology) if any is used to solve similar problems (I am a J2EE/java developer):

problem: Out of a probable set of words, with a given rule (say the word can be a combination of A and X, and always starts with a X, each word is delimited by a space), you have to read a sequence of words and parse through the input to decide which of the words are syntatctically correct. In a nutshell these are problems that involve parsing techniques. Say simulate the logic of an vending machine in Java.

So what I want to know is what are the techniques/best approach to solve problems pertaining to parsing inputs. Like alien language processing problem in google code jam

Google code jam problem

Do we use something like ANTLR or some library in java.

I know this question is slightly generic, but I had no other way of expressing it.

P.S: I do not want a solution, I am looking for best way to solve such recurring problems.

score 2 · Accepted Answer · answered Dec 29 '11 at 16:52

2

You can use JavaCC for complex parsing.

For relative simple parsing and event processing I use enum(s) as a state machine. esp as a push parser.

For very simple parsing, you can use indexOf or split(" ") with equals, switch or startsWith

answered Dec 29 '11 at 16:52

Peter Lawrey

525,659
79
751
1,130

are you talking about approach like this: http://www.javacodegeeks.com/2011/07/java-secret-using-enum-to-build-state.html – Ayusman Dec 29 '11 at 16:54
Since I write it, I did have that in mind. ;) The second half is an example of using an enum as a state machine. – Peter Lawrey Dec 29 '11 at 16:57
great Peter.. +1, I did try it in past, but could not understand it well. Let me try again. – Ayusman Dec 29 '11 at 17:17
Happy to take any specific questions if you have any simple examples. – Peter Lawrey Dec 29 '11 at 17:23

score 1 · Answer 2 · edited May 23 '17 at 12:16

If you want to simulate the logic of a something that is essentially a finite state automation, you can simply code the FSA by hand. This is a standard computer science solution. A less obvious way to do this is to use a lexer-generator (there are lots of them) to generate the FSA from descriptions of the valid sequences of events (in lexer-generator speak, these are called "characters" but you can cheat and substitute event occurrences for characters).

If you have complex recursive rules about matching, you'll want a more traditional parser. You can code these by hand, too, if the grammar isn't complicated; see my ?SO answer on "how to build a recursive descent parser". If your grammar is complex or it changes quickly, you'll want to use a standard parser generator. Other answers here suggest specific ones but there are many to choose from, all generally very capable.

[FWIW, I applied parser generators to recognizing valid transaction sequences in 1974 in TRW POS terminals the May Company department store. Worked pretty well.]

Avdhesh Yadav · Answer 3 · 2017-02-17T06:40:11.640

0

You can use ANTLR which is good, It will help in complex problem But you can also use regular expressions eg: spilt("\\s+").

edited Feb 17 '17 at 06:40

answered Feb 17 '17 at 06:12

Avdhesh Yadav

33
7

preferred language/technique for sequence processing or parsing

3 Answers3