We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

8

A brief answer is "by ignoring them". A compiler may scan the entire code more than once, but of course at least once in which case we call it a single-pass compiler. The task of lexical analyzer (or sometimes called simply scanner) is to generate tokens. This is done simply by scanning the entire code (in linear manner by loading it for example into an ...

6

Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that? If by "right" you mean it is the case in every programming language, then no, it is not right, and probably no non-trivial lexical statement would be either. In many languages, integer literals do not have to be separated from a ...

4

Compiled lexical analyzers compile the NFA to a DFA. Good interpreted regular expression matchers, on the other hand, use Thompson's algorithm, simulating the NFA with memoization. This is equivalent to compiling the NFA to a DFA, but you only produce DFA states on demand, if they are needed. At each step your deterministic state is a set of NFA states, ...

4

I see only two applications of using an NFA (or rather its power automaton without writing it down) instead of a minimized DFA: Homoiconic languages, where you may want to modify your lexer frequently Strange syntax that may blow up your DFA like identifier := [a-z][a-z0-9_]* indices := [0-9_]{1,256} //up to 256 times var := identifier "_" indices | ...

4

You can do concatenation with an epsilon transition, but it is not necessary. Many implementations avoid it because concatenations are common and the epsilon transitions significantly increase the machine size. There is some​ nice code in Russ Cox's famous essay on regular expressions, which implements a common strategy: fragment machines are built without ...

4

In your example, think of the result as having filled four slots: _ _ _ _, each of which can take one or three substrings, namely 0, 1, or the empty string. Ignoring the empty strings, it's clear that there are sixteen possible results: 0000, 0001, 0010, ... , 1111. With the empty strings, though, since we could make 10 by $(\epsilon)(\epsilon)(1)(0)$, or ...

3

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ ...

3

Speed and simplicity. A regular expression is a compact and declarative specification of lexemes. For most realistic regular expressions, simply writing code to mimic that specific regular expression would likely be something like an order of magnitude longer and less clear. This is especially true if you want high-performance. A regular expression, on the ...

3

How do hand coded lexers generally work? That depends on whose hand coded them :-). But: Are they similar to either table-driven or direct-coded ones? Table-driven hand-coded lexers are rare in my experience (if you were going to use a table anyway, why not use a tool to generate the table). Torczon & Cooper use "direct-coded scanner" to mean a ...

3

You don't use CFGs because typically lexical analysis can be performed using regular automata, and these are faster than context-free parsers. It's a question of efficiency.

3

I don't know what is the proper name for what you're seeing, but it is the standard way to lexically analyze text. You divide it into tokens of specific types. For the sake of context-free parsing (the next step in the parsing chain), you only need the type of each lexeme; but further steps down the road will need to know the semantic content (sometimes ...

3

I'd be surprised if they did. The construction of the lexer is done once (hopefully), the result used millions of times (just think how many tokens there are in your medium-sized source file). So, unless there are very unusual circumstances, it pays off to make the lexer as fast (and other resource frugal) as possible, i.e., go for a minimal DFA.

2

Typical lexers will return a sequence of pairs, where the pair consists of the token type and an optional value. For a token such as 12345, the token type will be something like "number" and the value will be 12345. If the lexer only emitted the information that there was a numeric constant in the input, then the following phases of the parser would have no ...

2

The strings not processed successfully are 1, 2, and 3. Only string 4 is processed successfully. I think your problem is not with interpreting the meaning of regular expressions, but in understanding the process of lexical analysis, at least as intended in your course. Normally, a regular expression is supposed to match a string from beginning to end. But ...

2

There is no need for an epsilon transition, it is a waste of space. For a regular expression $E$, with resulting automaton $A$, must respect these properties of the transition function, $\delta$: $A$ has exactly one initial state $q_0$, which is not accessible$^{*}$ from any state. That is,  \delta(q, a) \neq q_0 \quad \forall q \in A, \forall a \in \...

2

There are two ways to handle this issue: The most common implementation (the one used in lex, flex and other similar scanner generators) is to always recall the last accept position and state (or accept code). When no more transitions are possible, the input is backed up to the last accept position and the last accept state is reported as the accepted token....

2

* means that any number (including zero) of preceding expression can occur + means that at least one instance of preceding expression must occur

2

Yes. These are two different words for the same thing. I've also heard it called a lexer sometimes.

2

Regular languages are faster to recognize, and so they are preferred whenever possible. Fortunately, regular expressions are usually good enough for describing the lexemes of a language. Indeed, in some sense the separation between lexical analysis and parsing is exactly due to this fact, that lexical analysis can be done more efficiently than parsing.

1

There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's necessary to do so, and it's not because it's efficient to do so. Thompson's construction has the following advantages: It's recursive on the structure of the regular expression. It's easy to convince yourself that the ...

1

In C, 458cat is a single ppnumber token. It's not a valid number, so it will eventually produce an error message, but it is tokenised as a single token. There's a longer explanation of this behaviour in this StackOverflow answer.

1

Briefly, lexical analyzer reads source code character by character and generates tokens. It does not care about in what order tokens are generated. Relationship between tokens are checked by syntax analyzer and specified by a context free grammar. Let me give you a simple example. Consider the following piece of code int while = 5 Lexical analyzer emmits ...

1

The important fact in this case is that the list append operation is associative. Hadoop has "tokenize" as one of its built-in parallel operators. The meaning of "tokenize" in this case is much less general than "lexical analysis". They mean "splitting a string at a specific well-defined set of `delimeter' characters." I doubt there is much you could do ...

1

No, the symbol table could only keep an "identifier" for the number. E.g. if 56 it's the first integer met then a possible id could be "iconst_1". The numbers, as number are stored either in the memory or the Abstract Syntax Tree (AST). If numbers appear as initializations (e.g. int array[3] = {0} in C), then they initialize the array in where you allocated ...

1

What the compiler stores in the symbol table is whatever it needs to do its job of code generation. The value of the number certainly is a must. Other data might include stuff like small/large (small numbers might have shorter representations, or be included inline in instructions).

1

What you see there is a common regexp syntax. [ \t\n] matches any character that is a space, a tab or a new line. [a-zA-Z_][a-zA-Z0-9_]* matches any string of length at least one consisting of roman letters, digits and underscore that does not start with a digit. [0-9]+\.[0-9]* matches any number with at least one digit before the (mandatory) period. [0-9]+...

Only top voted, non community-wiki answers of a minimum length are eligible