• Home
 · 
• String Manipulation
 · 
• Parsing Concepts and Algorithm techniques (PART 1)

Parsing Concepts and Algorithm techniques (PART 1)

Explores and teaches parsing algorithm techniques (PART 1)

Rate Parsing Concepts and Algorithm techniques (PART 1)

• 1
• 2
• 3
• 4
• 5

(7(7 Vote))

Parsing concepts & Parsing Algorithms
INTRODUCTION (about this article)
	In this article, I will be looking at the concepts of parsing and parser construction. This article is not meant as a tutorial, or a discussion article, but rather a mix of the two. I will explore mostly the most commonly used and simplest (yet efficient) parsing method - Left to Right / Top to bottom parsing. In this example I will include a few examples for use with Visual Basic. In fact, this article is based around parsing using VB, and will review standard string manipulation functions for people who may not be familiar with them. Please note that I am 15 years old, but I’ve been programming in VB for 3 years and now use C and C++ as well. (I’d recommend building any complex parsers in C or C++, due to faster processing speeds, although VB.NET has sufficient processing speed for a large array of parsing tasks.)

PARSING IS looking through a string (a "sentence" or set of characters) and interpreting it as commands, or translating it, or basically setting up reactions when certain "sets" of characters are encountered or found.
 
 
SECTION 1 - String Manipulation
	Ok, first of all, I will run you through a review of string manipulation functions and string parsing methods (InStr, Mid, Left, Right, Ucase, Lcase etc.) if you’re already familiar with these functions, you can skip this part and proceed to section 2. As you hopefully already know, a string is a set of characters from the ASCII character set, for example "The Quick Brown Fox Jumped Over The Lazy Dog" is a string.
In parsing, you obviously work with these strings a lot. I will discuss the elements of parsing in SECTION2, but this is just to look over how we "look" ata string. First of all, these are the string manipulation functions available in VB (some may only be available in VB6, I’ve tried to note the ones that are)
*	Mid	-	For getting a set of characters from the middle of a string.
*	InStr	-	For Searching in one string for an occurrence another string (returns the position of the found string).
*	Left	-	For extracting the leftmost character(s) from a string.
*	Right	-	For extracting the rightmost characters from a string.
*	Replace	-	To replace one set of characters with another (VB6 and up only).
*	Len	-	For getting the length of a specified string.
 
I wont dive to deeply into how to use these function’s syntax, you can refer to the VB help file in the Strings category to find a full set of instructions and examples on how to utilize these. Although we WILL be exploring the use of these functions, and at that time I will explain how to use them properly.
 
SECTION 2 - Types of parsers
	There are two different types of parsers, and I’m not talking about the method in which they parse. I will call them Translator Parsers, and Command Parsers (there may be other types but I’m sticking to these two) Translators are converters, they take the data they are given and output new data. A compiler would be a perfect example of a translator, it takes the computer syntax and translates it into machine code.
 A command parser is a parser that actually does something when it interprets a certain "Command" - for a good example would be a script executor, it finds a command in the script, and it does convert the syntax to a string, instead, it executes a command or subroutine)
 
SECTION 3 - The FIVE parts of a parsing algorithm
	I have divided parsing algorithms into 5 basic parts to allow you to better understand the process of parsing a string. They are each defined below…
INPUT - The data that is given to the parser, usually a string. This is the data that the parser will parse through and will work with in the first place.
OUTPUT - The output is what the end product is (and maybe I should of put this part last in the list) it is what we lend up with after the parsing is complete. The output only exists if the parser is meant to conduct some sort of "translation" of the input (translation parsers take data and output other data accordingly, for more info on types of parsers, see section 2). Like if the parser’s purpose was to reverse all the letters in a sentence then the output of "Hello World" would be "dlroW olleH" - the input was "Hello World" and the output was "dlroW olleH".
INTERPRETATION - How the parser interpret the input. Does it see it as a set of commands, or as a language to be translated, what does it look for, what is It trying to find, and what will it do when it finds it. (see section 2 if you haven’t read it already and don’t get what I’m talking about here.)
PROCESSING - What the parser does once it interprets the data, for example, in the VB parser, when it finds the string "MsgBox" it knows that it will be displaying a message box, and the process it takes is looking for the message box properties. Then, after finding the properties (Caption, Buttons, Icon etc.) it displays a message box accordingly. Processing can add to the output depending on what it finds, or it can react, like the message box example, and interpret strings as commands.
 
SECTION 4 - Constructing a parser…
	Yeah! We’re finally past all that boring $hit about parts of a parser and stuff!!! In this section, we’re gunna build a parser to execute our own message box script. Go into VB and create a new project and a form and place a textbox on the form and a command button, put he buttons Caption to Execute and make the button’s name "CmdExe" and keep the name of the textbox as the default "Text1".
Now we’re gunna construct the parsing algorithm… When writing an algorithm of any sort, its good to figure out what steps the computer will need to take, or in mathematics, what equation the computer will use. In our case here, we’ll say that in our new script, the code for a message box is MSB followed by the properties in some angel-brackets then the caption in quotes – something like this…
MSB<"Hello World!">
So the first thing we did was figure out what the script might look like (which is a good idea for any type of script or language designing)
 Ok, so what are we gunna do to turn this little script into a message box? – here’s what…
  First of all, we need to find the string that tells us to make a message box – in this case, we’re looking for "MSB" so here’s what we put I our code.
‘---------------------------------------------------------------------
Private Sub CmdExe_Click()
 Dim CP 'CP will keep track of the
 'Position of the command
 
  CP = InStr(1, UCase(Text1).Text, "MSB")
  'ok, now CP will know the position of the word "MSB"
  'note that we used UCase(Text1.Text) which converts the string
 'in text1 to all uppercase so we don’t have to worry about
 'case sensitivity
End Sub
‘----------------------------------------------------------------------
Now we’ve found the command we’re looking for, this type of parsing isn’t top to bottom parsing, this type is just finding any possible commands. We should check to make sure the script has a ‘ <" ’ and a ‘ "> ‘. So we’ll do that and if we know they have put it in, we’ll need to find the caption of the message box, otherwise give them an error message! We’ll be storing the caption for further use as a variable. We can call our variable "MBCap" so here’s what the code will look like now…
‘----------------------------------------------------------------------
Private Sub CmdExe_Click()
 Dim CP, CP2, CP3, CP4 'CP will keep track of the
 'Position of the command
 Dim MBCap As String 'Stores the caption of
 'the message box for further use
 
  CP = InStr(1, UCase(Text1.Text), "MSB")
   If CP = 0 Then Exit Sub 'if we dont find it, discontinue
  'If we found it it will continue
  'ok, now CP will know the position of the word "MSB"
  'note that we used UCase(Text1.Text) which converts the string
 'in text1 to all uppercase so we dont have to worry about
 'case sensitivity
  'NOW WE CHECK FOR THE <" and ">
 CP2 = Mid(Text1.Text, CP + 3, 2) 'this selects the 2 characters directly
 'after the word MSB
 'check for the second
   CP3 = InStr(CP + 5, Text1.Text, Chr(34) & ">")
   CP4 = Mid(Text1.Text, CP3, 2)
   
  If CP2 = "<" & Chr(34) And CP4 = Chr(34) & ">" Then
  'the if says if we found <" and "> the continue
   Else
     Exit Sub 'otherwise discontiue with this sub
  End If
End Sub
‘-----------------------------------------------------------------------------
 As you more advanced programmers can see, I haven’t been the most efficient, but this is just one of thoughs things where simple is better. Now we need to extract the caption of the button, so this is how we do that, we’re gunna find the length of the caption by subtracting the position of the "> from the position of the ">, then we’ll select the caption and store it as a string for later use.
Now this is what the code should look like… (Copy it into your program, be sure to study it though)
‘-------------------------------------------------------------------------------
Private Sub CmdExe_Click()
 Dim CP, CP2, CP3, CP4 'CP will keep track of the
 'Position of the command
 Dim MBCap As String 'Stores the caption of
 'the message box for further use
 Dim CapLen As Integer 'stores the captions length
 
  CP = InStr(1, UCase(Text1.Text), "MSB")
   If CP = 0 Then Exit Sub 'if we dont find it, discontinue
   'If we found it it will continue
  'ok, now CP will know the position of the word "MSB"
  'note that we used UCase(Text1.Text) which converts the string
 'in text1 to all uppercase so we dont have to worry about
 'case sensitivity
  'NOW WE CHECK FOR THE <" and ">
 CP2 = Mid(Text1.Text, CP + 3, 2) 'this selectd the 2 characters directly
 'after the word MSB
 'check for the second
   CP3 = InStr(CP + 5, Text1.Text, Chr(34) & ">")
   CP4 = Mid(Text1.Text, CP3, 2)
   
  If CP2 = "<" & Chr(34) And CP4 = Chr(34) & ">" Then
  'the if says if we found <" and "> the continue
   Else
     Exit Sub 'otherwise discontinue with this sub
  End If
CapLen = CP3 - (CP + 5)
 MBCap = Mid(Text1.Text, CP + 5, CapLen)
 MsgBox MBCap
End Sub
‘--------------------------------------------------------------------------------
NOW if you run it and type MSB<"Hello WORLD!"> in the textbox, press execute and you get a message box with ‘hello WORLD!’ on it!
 I got tired hands, and I’m only 15, and I have school, so I’ll continue this tomorrow, happy programming, please vote!