{"id":34,"date":"2018-07-19T10:22:10","date_gmt":"2018-07-19T10:22:10","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=34"},"modified":"2022-01-06T11:27:56","modified_gmt":"2022-01-06T11:27:56","slug":"lexical-phase-regular-expression","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/lexical-phase-regular-expression\/","title":{"rendered":"Lexical phase \u2013Regular expression"},"content":{"raw":"
\r\n\r\nLexical Phase \u2013 Introdction\r\n\r\n \r\n\r\nThe objective of this module is to get a clear understanding of the lexical phase and to learn about defining patterns using regular expression.\r\n\r\n \r\n

This module discusses the functionalities of the lexical phase of the compiler. This will brief why we need lexical phase, what it does and how to do it efficiently.<\/p>\r\n \r\n\r\n3. 1 Functions of the Lexical Analyser<\/strong>\r\n\r\n \r\n

The main job of the lexical phase is scanning and lexical analysis. Scanning is the first part which helps in removal of comments and compaction of consecutive white space characters into single white space. The second part is the lexical analysis which is more complex. This part of the lexical phase helps in producing tokens. The input to this phase is the high level language text file and output will be a sequence of tokens. After this phase, the input text file no longer exists and is split into tokens to be passed on to the next phase of the compiler. In the process of splitting the input into tokens, the lexical analyser does the following functions:<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Identifies language keywords and standard identifiers\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Handles include files and macros\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Counts line numbers\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Removes whitespaces\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Reports illegal symbols\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Creates symbol table\r\n\r\n \r\n

Lexical analyzer does not have to be an individual phase. But having a separate phase simplifies the design and improves efficiency and portability. With these things in mind and in order to efficiently do these functions, the lexical analyser is not assigned a single pass of its own, rather<\/p>\r\n\r\n<\/div>\r\n

the lexical and the syntax analyser together functions as one pass and is specified in Figure 3<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

\r\n

From figure 3.1, it could be understood that, the lexer and the parser are combined together into one pass, where the parser issues a \u201cNexttoken()\u201d command and the lexer issues or gives a token to the parser. The grouping of the phases helps in achieving the following:<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Simplifies the syntax analysis in terms of language definition<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Enhances modularity and supports portability. It helps in using the same analyser-parser combination for various high-level languages across platforms as the analysis phase is target independent.<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Reusability\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Efficiency\r\n\r\n \r\n\r\n3.2 Definitions<\/strong>\r\n\r\n \r\n

Let us look at some basic definitions pertaining to the lexical phase of the compiler. Token is a group of characters having a collective meaning. Lexeme is a particular instant of a token. For example, consider the variable \u201cpi\u201d. So, token could be thought of as a name given to a lexeme. For this variable the token is \u201cidentifier\u201d and the corresponding lexeme is \u201cpi\u201d. Similarly for the string \u201cif\u201d, the lexeme is \u201cif\u201d and the token is \u201ckeyword\u201d. The lexemes are typically described by defining a pattern for it. The set of rules describing how a token can be formed is defined as its pattern. So, defining patterns for every possible lexeme is one of the main jobs of this phase of the compiler. For example, for the token identifier the pattern is [a-z]|[A-Z]) ([a-z]|[A-Z]|[0-9])*. Here, this corresponds to a regular expression. The operator \u201e[\u201e and \u201e]\u201f indicates that any one character in this range could be used. The operator \u201e|\u201f is the union operator. It indicates either this or that. The * is a Kleene closure operator which indicates zero or more combination of the symbols that has this operator. The implicit operator here is the concatenation operator \u201c.\u201d which indicates the sequence of symbols that occur. We will discuss more on defining regular expressions in the subsequent sections.<\/p>\r\n\r\n<\/div>\r\n3.2.1 Issues<\/strong>\r\n\r\n \r\n

Tokenizing is the primary job of this phase of the compiler. Hence, the primary issue is to find out how to identify tokens? Typically tokens are identified by defining patterns either as a regular expression or as an automata. The next issue is how the lexical phase will recognize the tokens using a token specification. This indirectly poses ways of implementing the nexttoken() routine. In order to solve these issues, the first two phases of the compiler are integrated.<\/p>\r\n \r\n\r\n3.2.2\u00a0\u00a0\u00a0 Lexical Analysis Problem<\/strong>\r\n\r\n \r\n

Formally stating, given a set of token descriptions in terms of token name and regular expression defining the pattern for a lexeme, the lexical phase accepts an input string and partitions the strings into tokens (class, value). In choosing the lexeme, there could be two matching prefix that would be a part of two different tokens. For example, consider the operator \u201c**\u201d for exponentiation. Will the compiler, consider this is as a multiplication operator on seeing the first \u201c*\u201d and will it log the second \u201c*\u201d as an error? It considers this as an exponentiation operator because it tries to match the longest matching prefix. Thus ambiguity encountered in this phase is typically resolved by choosing the longest matching token and between two equal length tokens, the first one is selected. Table 3.1 lists some examples of tokens and their corresponding example lexemes.<\/p>\r\n \r\n\r\nTable 3.1 Few Examples of Tokens and their description.\r\n\r\n\"\"\r\n

\r\n\r\n2.3<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Token Attributes<\/strong>\r\n\r\n<\/div>\r\n \r\n

A token is represented along with its attribute. A typical attribute is a pointer to the symbol-table entry in which the information about the token is populated. Consider the following example<\/p>\r\n \r\n\r\n\r\n\r\n
E=M*C**2<\/td>\r\n\u00e0 (3.1)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nFor the statement in (3.1), the lexemes are \u201cE\u201d, \u201c=\u201d, \u201cM\u201d, \u201c*\u201d, \u201cC\u201d, \u201c**\u201d, \u201c2\u201d.\r\n\r\n \r\n\r\nThe tokens and the their attributes are listed below\r\n\r\n \r\n\r\n<id<\/strong>, pointer to symbol-table entry for E>\r\n\r\n \r\n\r\n<assign_op<\/strong>,> - attribute since it is a keyword indicating the operator\r\n\r\n \r\n\r\n<id<\/strong>, pointer to symbol-table entry for M>\r\n\r\n \r\n\r\n<multi_op<\/strong>,> - attribute since it is a keyword indicating the operator <id<\/strong>, pointer to symbol-table entry for C>\r\n\r\n \r\n\r\n<exp_op<\/strong>,> - no attribute since it is a keyword indicating the operator <num<\/strong>,integer value 2>\r\n\r\n \r\n

3.2.4 Patterns: <\/strong>The lexical phase, decides the token based on defining patterns. Let us look at how to define patterns using regular expression. Table 3.2 gives the basic idea about the basic patterns of a regular expression.<\/p>\r\n \r\n\r\nTable 3.2 Basic regular expression\r\n\r\n\"\"\r\n

<\/div>\r\n
    \r\n \t
  • \"\"<\/li>\r\n<\/ul>\r\n\"\"\r\n

    comments but constructing automata may be easier. In this context, it is to be understood that the language generated by an automata and the regular expression refers to a class of languages called regular language. Defining automata is easier rather than stating regular expressions. There is another option to combine both and specify partial automata with regular expressions on the edges. This doesn\u201ft require us to specify all the possible states but specify different actions at different states. As far as the automata is concerned a deterministic finite automata (DFA) is faster in string matching. However, constructing a DFA is difficult. Therefore, we create non-deterministic finite automata (NDFA) from every regular expression using an algorithm. Merge all the automata using epsilon moves (like the | construction). Then from the NDFA construct a DFA using another algorithm and then use a procedure to minimize the automaton starting with separate accepting states.<\/p>\r\n \r\n\r\n3.2.7 Automata<\/strong>\r\n\r\n \r\n\r\nAutomata typically refer to a Deterministic one. It is a five tuple representation (Q, \u2211, \u03b4, q0, F), where q0 belongs to Q, Q is a finite set of states, F is a subset of Q indicating final states,\r\n

      \r\n \t
    • \u03b4 is a mapping from Q x \u2211 to Q. The transition function states, for every state on every input symbol there is exactly one transition. We define the language of the automata as<\/li>\r\n<\/ul>\r\nL = {w | \u03b4 (q0, w) = r, r is a subset of F}.\r\n\r\n \r\n

      The interpretation of this definition is that, the string \u201cw\u201d should take you from the start state q0 to any one of the final state. Hence, every string has exactly one path and so a DFA is faster for string matching. On the other hand, a NFA is similar to a DFA, but it gives some flexibility. It is a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q, F is a subset of Q and \u03b4 is a mapping from Q x \u2211 to 2Q . The transition function here indicates that for every state on every input symbol there could be 0 or more transitions.<\/p>\r\n \r\n\r\nWe define the language of the NFA as\r\n\r\n \r\n\r\nL = {w | \u03b4 (q0, w) = R, where any one state of R is a subset of F}.\r\n\r\n \r\n

      Since, multiple paths exists because of the existence of multiple transitions, a NFA takes more time for string matching. \u03b5 -NFA is same as NFA but with more flexibility in allowing to change state without consuming any input symbol.<\/p>\r\n \r\n

      The definition of \u03b5 -NFA is different from NFA only in the transition function which is defined as \u03b4 a mapping from Q x \u2211 U { \u03b5 } to 2Q. Hence, it is slower than NFA for string matching.<\/p>\r\n \r\n

      Summary<\/strong>: This module focused on constructing regular expressions and regular definitions as a way of defining pattern for regular expressions which will be used by the lexical phase of the compiler.<\/p>","rendered":"

      \n

      Lexical Phase \u2013 Introdction<\/p>\n

       <\/p>\n

      The objective of this module is to get a clear understanding of the lexical phase and to learn about defining patterns using regular expression.<\/p>\n

       <\/p>\n

      This module discusses the functionalities of the lexical phase of the compiler. This will brief why we need lexical phase, what it does and how to do it efficiently.<\/p>\n

       <\/p>\n

      3. 1 Functions of the Lexical Analyser<\/strong><\/p>\n

       <\/p>\n

      The main job of the lexical phase is scanning and lexical analysis. Scanning is the first part which helps in removal of comments and compaction of consecutive white space characters into single white space. The second part is the lexical analysis which is more complex. This part of the lexical phase helps in producing tokens. The input to this phase is the high level language text file and output will be a sequence of tokens. After this phase, the input text file no longer exists and is split into tokens to be passed on to the next phase of the compiler. In the process of splitting the input into tokens, the lexical analyser does the following functions:<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Identifies language keywords and standard identifiers<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Handles include files and macros<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Counts line numbers<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Removes whitespaces<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Reports illegal symbols<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Creates symbol table<\/p>\n

       <\/p>\n

      Lexical analyzer does not have to be an individual phase. But having a separate phase simplifies the design and improves efficiency and portability. With these things in mind and in order to efficiently do these functions, the lexical analyser is not assigned a single pass of its own, rather<\/p>\n<\/div>\n

      the lexical and the syntax analyser together functions as one pass and is specified in Figure 3<\/p>\n

       <\/p>\n

      \"\"<\/p>\n

       <\/p>\n

      \n

      From figure 3.1, it could be understood that, the lexer and the parser are combined together into one pass, where the parser issues a \u201cNexttoken()\u201d command and the lexer issues or gives a token to the parser. The grouping of the phases helps in achieving the following:<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Simplifies the syntax analysis in terms of language definition<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Enhances modularity and supports portability. It helps in using the same analyser-parser combination for various high-level languages across platforms as the analysis phase is target independent.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Reusability<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Efficiency<\/p>\n

       <\/p>\n

      3.2 Definitions<\/strong><\/p>\n

       <\/p>\n

      Let us look at some basic definitions pertaining to the lexical phase of the compiler. Token is a group of characters having a collective meaning. Lexeme is a particular instant of a token. For example, consider the variable \u201cpi\u201d. So, token could be thought of as a name given to a lexeme. For this variable the token is \u201cidentifier\u201d and the corresponding lexeme is \u201cpi\u201d. Similarly for the string \u201cif\u201d, the lexeme is \u201cif\u201d and the token is \u201ckeyword\u201d. The lexemes are typically described by defining a pattern for it. The set of rules describing how a token can be formed is defined as its pattern. So, defining patterns for every possible lexeme is one of the main jobs of this phase of the compiler. For example, for the token identifier the pattern is [a-z]|[A-Z]) ([a-z]|[A-Z]|[0-9])*. Here, this corresponds to a regular expression. The operator \u201e[\u201e and \u201e]\u201f indicates that any one character in this range could be used. The operator \u201e|\u201f is the union operator. It indicates either this or that. The * is a Kleene closure operator which indicates zero or more combination of the symbols that has this operator. The implicit operator here is the concatenation operator \u201c.\u201d which indicates the sequence of symbols that occur. We will discuss more on defining regular expressions in the subsequent sections.<\/p>\n<\/div>\n

      3.2.1 Issues<\/strong><\/p>\n

       <\/p>\n

      Tokenizing is the primary job of this phase of the compiler. Hence, the primary issue is to find out how to identify tokens? Typically tokens are identified by defining patterns either as a regular expression or as an automata. The next issue is how the lexical phase will recognize the tokens using a token specification. This indirectly poses ways of implementing the nexttoken() routine. In order to solve these issues, the first two phases of the compiler are integrated.<\/p>\n

       <\/p>\n

      3.2.2\u00a0\u00a0\u00a0 Lexical Analysis Problem<\/strong><\/p>\n

       <\/p>\n

      Formally stating, given a set of token descriptions in terms of token name and regular expression defining the pattern for a lexeme, the lexical phase accepts an input string and partitions the strings into tokens (class, value). In choosing the lexeme, there could be two matching prefix that would be a part of two different tokens. For example, consider the operator \u201c**\u201d for exponentiation. Will the compiler, consider this is as a multiplication operator on seeing the first \u201c*\u201d and will it log the second \u201c*\u201d as an error? It considers this as an exponentiation operator because it tries to match the longest matching prefix. Thus ambiguity encountered in this phase is typically resolved by choosing the longest matching token and between two equal length tokens, the first one is selected. Table 3.1 lists some examples of tokens and their corresponding example lexemes.<\/p>\n

       <\/p>\n

      Table 3.1 Few Examples of Tokens and their description.<\/p>\n

      \"\"<\/p>\n

      \n

      2.3<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Token Attributes<\/strong><\/p>\n<\/div>\n

       <\/p>\n

      A token is represented along with its attribute. A typical attribute is a pointer to the symbol-table entry in which the information about the token is populated. Consider the following example<\/p>\n

       <\/p>\n\n\n\n
      E=M*C**2<\/td>\n\u00e0 (3.1)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

       <\/p>\n

      For the statement in (3.1), the lexemes are \u201cE\u201d, \u201c=\u201d, \u201cM\u201d, \u201c*\u201d, \u201cC\u201d, \u201c**\u201d, \u201c2\u201d.<\/p>\n

       <\/p>\n

      The tokens and the their attributes are listed below<\/p>\n

       <\/p>\n

      <id<\/strong>, pointer to symbol-table entry for E><\/p>\n

       <\/p>\n

      <assign_op<\/strong>,> – attribute since it is a keyword indicating the operator<\/p>\n

       <\/p>\n

      <id<\/strong>, pointer to symbol-table entry for M><\/p>\n

       <\/p>\n

      <multi_op<\/strong>,> – attribute since it is a keyword indicating the operator <id<\/strong>, pointer to symbol-table entry for C><\/p>\n

       <\/p>\n

      <exp_op<\/strong>,> – no attribute since it is a keyword indicating the operator <num<\/strong>,integer value 2><\/p>\n

       <\/p>\n

      3.2.4 Patterns: <\/strong>The lexical phase, decides the token based on defining patterns. Let us look at how to define patterns using regular expression. Table 3.2 gives the basic idea about the basic patterns of a regular expression.<\/p>\n

       <\/p>\n

      Table 3.2 Basic regular expression<\/p>\n

      \"\"<\/p>\n

      <\/div>\n
        \n
      • \"\"<\/li>\n<\/ul>\n

        \"\"<\/p>\n

        comments but constructing automata may be easier. In this context, it is to be understood that the language generated by an automata and the regular expression refers to a class of languages called regular language. Defining automata is easier rather than stating regular expressions. There is another option to combine both and specify partial automata with regular expressions on the edges. This doesn\u201ft require us to specify all the possible states but specify different actions at different states. As far as the automata is concerned a deterministic finite automata (DFA) is faster in string matching. However, constructing a DFA is difficult. Therefore, we create non-deterministic finite automata (NDFA) from every regular expression using an algorithm. Merge all the automata using epsilon moves (like the | construction). Then from the NDFA construct a DFA using another algorithm and then use a procedure to minimize the automaton starting with separate accepting states.<\/p>\n

         <\/p>\n

        3.2.7 Automata<\/strong><\/p>\n

         <\/p>\n

        Automata typically refer to a Deterministic one. It is a five tuple representation (Q, \u2211, \u03b4, q0, F), where q0 belongs to Q, Q is a finite set of states, F is a subset of Q indicating final states,<\/p>\n

          \n
        • \u03b4 is a mapping from Q x \u2211 to Q. The transition function states, for every state on every input symbol there is exactly one transition. We define the language of the automata as<\/li>\n<\/ul>\n

          L = {w | \u03b4 (q0, w) = r, r is a subset of F}.<\/p>\n

           <\/p>\n

          The interpretation of this definition is that, the string \u201cw\u201d should take you from the start state q0 to any one of the final state. Hence, every string has exactly one path and so a DFA is faster for string matching. On the other hand, a NFA is similar to a DFA, but it gives some flexibility. It is a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q, F is a subset of Q and \u03b4 is a mapping from Q x \u2211 to 2Q . The transition function here indicates that for every state on every input symbol there could be 0 or more transitions.<\/p>\n

           <\/p>\n

          We define the language of the NFA as<\/p>\n

           <\/p>\n

          L = {w | \u03b4 (q0, w) = R, where any one state of R is a subset of F}.<\/p>\n

           <\/p>\n

          Since, multiple paths exists because of the existence of multiple transitions, a NFA takes more time for string matching. \u03b5 -NFA is same as NFA but with more flexibility in allowing to change state without consuming any input symbol.<\/p>\n

           <\/p>\n

          The definition of \u03b5 -NFA is different from NFA only in the transition function which is defined as \u03b4 a mapping from Q x \u2211 U { \u03b5 } to 2Q. Hence, it is slower than NFA for string matching.<\/p>\n

           <\/p>\n

          Summary<\/strong>: This module focused on constructing regular expressions and regular definitions as a way of defining pattern for regular expressions which will be used by the lexical phase of the compiler.<\/p>\n","protected":false},"author":4,"menu_order":3,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-34","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/34","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":3,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/34\/revisions"}],"predecessor-version":[{"id":348,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/34\/revisions\/348"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/34\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=34"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=34"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=34"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}