Please enable JavaScript.

Coggle requires JavaScript to display documents.

Lexical Analysis image, image, image, image, image, image, image - Coggle…

- - - - For many programming languages, the lexical analyser can easily distinguisg between identifiers (or other names) and reserved words.
      - White space and comments have not been passed on as tokens. It is tempting to say that white spaces and comments are ignored but this is not strictly accurate.
      - There are three cases here two-character tokens where there is potential for confusion in their interpretation <=, += and ++.
      - The lexical analyzer makes no attempt to verify that this example contains a well-formed while statement.
  - - - Identifiers. Starting with a letter follower by an arbitrary sequence of letters or digits or underscores.
      - Integer constants such 12345. The language definition allows a wider range of integer, and optional suffices to specify that the constant is unsigned and/or long.
      - Character constants also can take several forms. The simple form is a single character enclosed between single quote marks.
      - Floating constants too can be expressed in several ways. The traditional representation is an integer part followed by a full stop followed by a fractional part.
      - String constants are sequences of characters enclosed by double quotes.
      - The operator tokens are numerous but somewhat simpler in structure. They take the form of a single character set and the automatic concatenation of adjacent strings.
      - Keywords and reserved words have special meanings in the syntax of the language. Reserved words are assumed to be keywords of the language.
      - Finally, although not tokens as far as the rest of the compiles is concerned, comments have to be parsed by the lexical analyzer o that they can be ignored.
  - - - Check the syntax, and endure that all possible forms of numerical constants are being dealt wih appropriately. It depends on the detail of the language being analysed but handling + or * as being part of the constant is rarely a good idea.
      - Reading and analyzing numeric constants for most languages will require lookahead.
      - Floating point constants may have a more complex syntax with a range of alternative representations.
- - - - Are upper case and lower case equivalent?
      - If the language has keywords, is the cas of letters significant?
      - Is there a limit on the leght of an identifier, and are all characters significants?
      - Is white space allowed within an identifier.
      - In some cases, the language specification may use the term "implementation-defined"
  - - - The set of possible lexical tokens returned by the lexical analyzer is definied as an enum type.
      - To make the code a little simpler, the lexical analysis function, lex, returns a single integer value rather than a structure containing in addition the source line number and the sting representations of the token.
      - To make the coding of the lexical analyzer manageable, we will make use of a one character lookahead.
- - - - Start with the regular expression. This can be transformed into a non-deterministic finite-state machine.
      - Because the implementation of a non-deterministic machine is complicated and potentially inefficient, the non-deterministic machines is transformed into an equivalent deterministic finite-state machine.
      - The deterministic finite-state machine thus generated may well have many more states than strictly necessary, and a process of state minimization is performed to ensure that the machine is the simplest possible for the parsing of instances of the original regular expression.
      - Unfortunately, this process is really not appropriate or carrying out by hand. The individual steps may appear simple but as soon as there is any complexity in the regular expression, the detail becomes overwhelming and t is very hard and time-consuming to produce a lexical analyzer with any hope of correctnes.
- - - - Programming by hand may be the only option because there may be no lexical analyzer generating tools available that are compatible with the programming language being used for the compiler's implementation.
      - The process of compiler construction is less dependent of the availability of other software tools, and there is no need to learn the language of a new software tool.
      - There are no real constraints on the techniques used for recognizing tokens because it is easy to add ad hoc code to deal with awkward analysis tasks.
      - The memory requirements of the lexical analyser can be modest. A lexical analyzer generated automatically ay be more memory hungry despite the effect of techniques for internal table compression.
      - Performance of the lexical analyzer produced in this way can be very good.
    - - Using a software tool purposely made for the job offers some significant benefits:
        
        The code is more likely to be correct, particularly for lexical tokens with a complex structure.
        
        Regular expressions specifications for the lexical tokens may be available in the language specification or documentation.
        
        The task of writing the lexical analyzer is potentially much simpler bacause much less code has to be writtenm
        
        The lexical analyzer is easy to modify.
        
        Permormance of the lexical analyzer producen in this way can also be very good.
  - - - DL is a simple language with a small set of easily-defined lexical tokens. We have already seen how a lexical analyzer for DL can be coded directly in C but is certainly wirth examining a different approach, using the lex tool.
    - - Although lexical analyzer generating tools are large and complex pieces of software, their use is not difficult.
      - The high-level structure of the input is simple. It consists of three sections, separated by lines containing just characters %%
      - The definition section consist of a set o name/definition pairs, used primarily to associate mnemonic names with regular expressions used in the rules sections.
      - The rules section is al ist of regular expression/corresponding C action pairs.
      - Finally, the user code section is copied directly to the output generated by flex and contains C functions which call or are called by the code in the rules section.
    - - What is the interface between the lexical analyzer and the syntax analyzer? Typically, the toen identity is encoded as an integer value and the "values" of tokens such as constants.
      - How are source lines beginning with # line directive has to be handled in th lexical analyzer.
      - There is a particularly nasty problem in the analysis of C in the handling of typedef names.
      - How is it best to handle reserved words? Having a separate regular expression for each reserved word is certainly possible, but it may be better to handle reserved words names using the same rule together with simple code to check whether the matched string is in fact a reserved word.
      - Are they constraints on the ordering of patterns in the rules section? Is there any potential ambiguity?
      - Are there regular expressions that could usefully be included in the flex definitions section to make the rules section more readable? This should become clear as the rules are developed.