Application of Regular Grammar in the Syntactic Analysis of Email Addresses

Formal definition of RGs

Regular grammar generates regular language. RGs have a single nonterminal on the left side and a right side consisting of a single terminal or a single terminal followed by a nonterminal. Formally, a grammar consists of a set of nonterminal (or variables) V , a set of terminals Σ (the language alphabet), a beginning symbol S, which is a nonterminal, and a set of rewriting rules (productions) P ⁷.

A right-hand regular grammar (also called a right-hand linear grammar) is a formal gramar (N, σ, P, S) in which all production rules in P have one of the following forms:

where A,B, and S ∈ N are nonterminal symbols, a ∈ Σis a terminal symbol, and ε denotes the empty string, i.e., the string of length 0. S is called the start symbol ⁸.

In a regular left grammar (also called a left linear grammar), all rules obey the following forms:

The language described by a given grammar is the set of all strings that contain only terminal symbols and can be derived from the start symbol via the repeated application of production rules. These two types of grammars have the same generative power, i.e., given a linear grammar on the left, there is always a linear grammar on the right that is equivalent to it, and vice versa. In addition, given a regular language, there is always (at least) a linear grammar on the left and a linear grammar on the right that generate it. There is no profound difference between left and right linear grammar.

A regular grammar is a quadruple (V,Σ,R, S), where:

• V is an alphabet of variables

• Σ is an alphabet of constants

• R, the set of rules, is a finite subset of V × (ΣV ∪ Σ)

• S, the initial symbol, is an element of V

This grammar, together with the set of rules, is determined under the elements of V − Σ, which are called nonterminals and are analogous to parts of speech. In the example, G = (V,Σ,R, S) where V = {S, a, b},Σ = {a, b}, and R has the rules S → aSb and S → ε.

Nonterminals are generally represented by capital letters and terminals by lowercase letters. Therefore, a context-free grammar can be given simply by providing the rules and the starting symbol without a tuple of 4. The above-mentioned grammar can be represented as:

Here is a derivation of this grammar.

Such a derivation has to eliminate the nonterminal. It is also possible to write this derivation as

Given a context-free grammar G, the language generated by G,L(G), is the set of terminal strings that can be derived from the initial symbol for G.

Syntax

• Email syntax

Each email address consists of three elements: the local part, the @ symbol (pronounced as ”at”), and the domain name. The local part is placed before the @ symbol, and the domain name is placed after it (9). An example of this is the email johndoe@company.com, where ” johndoe ” is the local part and ” company.com ” is the domain. Emails are not valid without these items.

parte_local@dominio

• Local part

The local part is the username that indicates a unique name for the mailbox. It can contain

• Uppercase and lowercase Latin letters (AZ, az)

• Numerical values (from 0 to 9)

• Special characters, such as #!% $ ’& + * -/=? ˆ_‘. {| }

It should be noted that the period character (.) Is valid for the local part unless it is placed at the beginning or the end of an email address ⁹. Moreover, there cannot be two or more periods in a row in the email address (e.g., John.. Doe @ company.com is not allowed).

The local postmaster part is treated in a special way: it is not case-sensitive and should be forwarded to the email manager of the domain ¹⁰. Technically, all other local parts are case-sensitive. Therefore, jsmith@example.com specifies different mailboxes, but many organizations treat uppercase and lowercase letters as equivalent. In fact, RFC 5321 warns that ”a host waiting to receive mail should avoid defining mailboxes where the local part is case sensitive"(p. 405) ¹¹.

• @ symbol

The @ symbol connects the domain and the person who owns the email address.

• Domain name

A domain name consists of one or more parts separated by a period, such as example.com ⁹. Each part must not be longer than 63 characters and can contain the following:

• Uppercase and lowercase Latin letters (AZ, az)

• Numerical values (from 0 to 9), with the condition that the entirety if the domain cannot be numerical

• A dash (-), as long as it is not placed at the beginning or end of the domain name

The domain name indicates the name of the organization. It is an address that leads to the organization’s website. When an email is sent, the sending mail server looks for another mail server that matches the domain name of the recipient’s address ¹¹. If someone sends a message to a user at company.com, the mail server first checks to see if there is a replying mail server at company.com. If so, it will contact the mail server to see if the username is valid. If the user is real, the email will be delivered.

• Standardization of local parts

The interpretation of the local part of an email address depends on the conventions and policies implemented in the mail server. For example, case sensitivity can distinguish mailboxes that differ only in the uppercase of the characters in the local part, although this is not very common ¹¹. Gmail ignores all dots in the local part of an @ gmail.com address to determine the identity of the account.

• Particularity

There is a particularity that is added to the RG: the words dot and at are accepted verbatim, making reference to the signs used in the English language. These must be found within the square brackets to be accepted as valid email addresses. In the case of parentheses, they are allowed at either end of the email address in the local part, and they will be identified as comments. With the above, the emails (comment)test@mail.com and test(comment)@mail.com are valid. Table I shows some examples of valid and invalid emails.

Table I: Valid and invalid emails

Construction of regular grammar

The RG for email addresses is as follows:

Chains W, where W ∈ L(M) and L(G). It is stated that L(M) or L(G) defines the language of grammar for W ⊆ ”All valid (not just common) email address structures”.

RG is formally represented as:

The rules established for the construction of the RG were elaborated based on the syntax of the RFC 5321 and 5322 regulations. Tables II and III present the rules described for the local part, the @ sign, and the domain name.

Table II: Characters valid for the local part and domain of the email

Table III: Special mail rules

Table II presents all possible characters (already explained) that can be generated, indicating that, when a period is detected, there must be continuity with at least one character, and, when the local part is finished, it must be followed by the @ sign. This is described in the states S,U, and A. For state X, this works in the same way as in the previous states, except for special characters. In this rule, a period may be needed, followed by other characters that accompany the domain, together with the opening of the square bracket (if that option is to be selected). After the period or without it, it is possible to have another combination of characters that includes the hyphen (valid by regulation). The rule can allow to continue writing after the script, moving on to the next one, which will no longer contain hyphens.

Table III corresponds to the period and the @ sign. The rule for accepting the expression dot (period) is added. It was also possible to determine the special case for accepting the word at (at).

After writing the characters comes a final character, since it is not possible for the domain part to contain a hyphen. The domain part ends with any character that is contained in the above-presented Tables, with the exception of the hyphen, as well as without continuing to any variable. The stack is made based on the construction of the RG, where, for each alphabet of the input symbols, the stack is filled or emptied depending on the states to which the automata goes. It can be seen, in Fig. 2, that there are more stack automata rules, which can be interpreted with the already explained grammar, considering that the stack will be eliminated as the conditions are met.

Figure 2: Generated stack automaton

The construction of the algorithm is carried out in two files, which contain the graphical user interface and the logical part of the email validation.

Application

This GUI was developed with the Tkinter package, which is a binding of the Tcl/Tk graphic library. The above is not a single library but consists of a few different modules, each with a separate functionality and its own official documentation for easy interface construction. This was done under the Model-View-Controller design pattern, in which the program is initialized along with its corresponding screen. In the model, the validateMail class is called to validate an email. If everything is correct, it Will return the value with the email; otherwise, it will show an error message with the email.

a. Algorithm implementation

In the logical part, the definition of global variables is proposed, describing the grammatical rules that must be fulfilled. These include lowercase and uppercase letters (using the upper function), numbers, special characters, the acceptance of symbols such as @ and the period, and adding square brackets.

When entering the validate function, a series of validations begins, such as the number of @ in the email and whether it contains atoms. Then, the mail is divided into two parts for verification, both the local part and the domain part, performing the corresponding iterations character by character. All the messages that are obtained in the results are stored in a list, from which it Will be verified if the last two messages indicate that the email complies with the regulations. Next, test scenarios aimed at validating the application are presented, with the help of some of the classes that contain the main algorithm. This is done in different scenarios and under the input of several email addresses.

• Scenario 1

When the program starts, it executes and creates the model instances with an example mail, together with the window with its size and the controller. The model carries out the instance by calling the main class, in which the email is verified. In this instance, the validation of the messages in the main class is performed by the stack. For an email to be valid, the last two messages are stored in an auxiliary variable, which will contain the last two positions, which would indicate the last two messages, as shown in Fig. 3a. For an email to be valid, it must have the message .OK.or .OK 2"; otherwise, it can indicate a message, such as the repetition of the @ character, two periods in a row, that the @ sign exists, or that it does not comply with any of the rules. This can be seen in Fig. 3b, for which the result will be shown in the console with both a valid email (first line) and an invalid email (second line).

Figure 3: Instance of the validateMail class with results in the console

• Scenario 2

The algorithm contains the validateMail class, for which the validate function is entered and the string of characters from the mail is received. In the first case, the validation of the number of @ or (at) expressions is carried out. Assigning the message to the end of the queue indicates that the rule of @ is not being fulfilled. It will be given by finishing the execution of the class; otherwise, it will go to another function in which validations are performed for the local part and the domain. The validation of the @ sign can be seen in Fig. 4a along with the result obtained when executing it (Fig. 4b).

For the case where the number of characters is verified, which cannot exceed 64, the message is added to the final part of the already created queue. At this point, two messages are returned: the first would indicate the error, and the second the entry to a cycle. For the mail to be valid, it must have two messages with validation at the end of the queue.

Figure 4: Validation of the number of @ and of characters (a) with their corresponding results for each case (b)

If the number of @ in the email is met, then it will move on to the validation function, which receives the string of characters for the email. In this case, two things can occur: if it contains @, another series of validations are performed, and another function of the algorithm changes on; otherwise, it is indicated that the @ symbol is not present, since it was not detected in the path of characters. Unlike the previous function, by regulation, this one checks the location of the symbol at the beginning or at the end of the chain. If the email does not contain an @ sign, the message indicating the error is added to the bottom of the list. If everything is correct in the previous validation, an enumerate loop is entered, which iterates the chain, given that, in Python, the chain is an array and, therefore, it can be traversed. If a string goes to enumerate, the output will show the index and value of each character in the string.

It should be noted that the algorithm only uses a library, which complements the function in which it receives double quote or parenthesis characters, indicating whether all its elements are the same in a list and working in the case that comments are contained between parentheses and one desires to validate that only letters have been written in the string.

• Scenario 3

If the local part of the email has less than 64 characters, the validate_character_local function will be called, which will verify the local part of the string and evaluate its characters one by one. With this function, several results can be returned: if the characters are letters, numbers, and special characters, the returned value will be True, whereas, for periods and @, 3 or 4 will be returned. This can be seen in Fig. 5a. The above is done with lists that contain all the valid letters, numbers, symbols, and characters that comply with the grammar rules. In some cases, validation is carried out with the zip function, which can go through several lists in the same iteration, working for the lists of uppercase and lowercase letters, along with the dot-at-sign list. The characters are entered one by one, validating whether they are in any of the lists and returning the corresponding value; otherwise, False will be returned, i.e., the result shown in Fig. 5b.

Figure 5: Validation of rules according to regulations and their results

If 3 is returned in the previous function, validation ensures that there are no repeated periods regarding their specific position with a loop, which allows the chain to be within a collection. Thus, if the route of the chain is found with two periods in a row, it will add the corresponding message to the list, iterating both in the previous position and in the current one. The validation also works for a period followed by an @ sign; the error is added to the last message, and the execution of the class ends. In this case, the validation of the local part is carried out, and the iteration is carried out with @.

Now, if the function returns 4, the message that an @ sign was detected is added to the list. If the email ends with @, an error will be displayed. After adding the message, the validate_domain function is entered, which receives the mail along with a number, which will indicate the cycle it must enter, be it 1, identifying the @ character, or 2, identifying the string ”(at). The above Will depend on the result given in the validate_character_domain function. Then, in the same way, it is verified whether the periods are repeated or there are consecutive periods and @. If the rules are met, the message ” OK 2” is added to the list, indicating that the domain part was successfully validated.

If 2 is returned in the validate_domain function, the string has been found to contain "at", which is a special handling rule. From the above, the chain enters the functions 3 and 4, where the first function, which separates the local part of the domain with split, divides each time it finds a square bracket - if it contains more than one ( dot), several separations of the string have to be performed. The first one contains the domain part, together with ”at", and is stored in separate_- one, resulting in ”at domain.com". Now, a new division is carried out, but the separating carácter is the square bracket "", in order to obtain only the part of the domain. This is stored in a variable to be able to return it.

Upon receiving the character 1, the string is separated with the identifier of the @ sign using the split function, which receives the character in which a string is going to be separated, storing it in a list, and, if it only contains one @, then the separation is saved in two positions in the list. The first is for the local part, and the second is for the domain part, given that the variable will apply the second position to perform the domain validation. Again, as the local part is in a variable, it is verified whether it has no more than 64 characters; if it does not contain them, the function validates_character_domain receives the part of the domain and performs the same validations of letters, numbers, and periods with @, adding the possibility that the domain may have an underscore. Finally, the last two positions of the list are returned to indicate their result in the corresponding iterations and validations of each function, so that, in the App class, it can be verified whether the valid characters are contained in the last two validations.

According to the aforementioned validation, the GUI can show the result for the typed email (correct or incorrect). Here, there are two functions for each of these two messages, which are identified with colors so that the user can easily see if the result was satisfactory (text in green) or not (text in red), obtaining in a variable the email entered from the function knows from the controller. Note that self represents instances of the classes and is used to obtain what is stored in each of the variables. In this way, it is possible to carry out the validation of an, as shown in Fig. 6b.

Figure 6: Functions to show the result in the graphical interface

The grammar rules were established in global lists at the beginning of the code, so that they could be used in all the functions, allowing them to be used throughout the code without having to redefine them, as well as to work with the established values. The rules for the types of letters, numbers, special characters, @ and period rules, and lines were applied to each list (Fig. 7).

Figure 7: Grammar rules implemented for the algorithm

b. Installing the generated library

To install the library, some characteristics are necessary, including the creation of the virtual environment with the corresponding command, within the folder for which the library will be used.

• Scenario 1

The package is installed via a terminal command through the Pypi repository, which searches its repositories for the indicated package and downloads it. After this operation, it is possible to use the package (Fig. 8a). If the package was installed correctly, no error will be found in IDE (Fig. 8b). The terminal will display the information corresponding to the package from which the query is being made.

Figure 8: Library installation and package validation

• Scenario 2

In this scenario, the utility of the library is accessed from the GUI. In it, the instance of the App class must be defined together with the call for the mainloop () function. After the above, the window is displayed, in which it is possible to write email addresses for validation (Fig. 9).

Figure 9: Using the library from the GUI

• Scenario 3

In this scenario, the library is used via the validateMail class, which uses its corresponding functions to enter the email address and show the result in the console: if the entry was valid, the result is Mail is correct; if not, it is Mail is wrong. This can be seen in Fig. 10. As seen in the previous scenarios, it was possible to use the library on another computer, either with the GUI or with the corresponding class, to be able to validate email addresses. In either case, the library complies with the RFC 5321 standard for the construction of an algorithm with regular grammars.

Figure 10: Valid and invalid emails

c. Algorithm effectiveness

When performing the validation of the library in real cases, its performance against the JFLAP program was verified. For this comparison of the number of executions vs. the effectiveness of results, tests were executed in both scenarios with the indicated number of 100 valid and 100 invalid addresses, with a certain increasing number of executions for them the results are presented in Table IV. This Table contains the information related to the valid and invalid emails applied in both parts. Note that the results should be the same.

Table IV: Execution results (library vs. JFLAP)

These results corroborate the performance of the algorithm. According to the standard deviation found for both the algorithm and JFLAP, when executing valid emails, the former has a lower dispersion than the latter. Fig. 11 depicts the results with their corresponding linear regression, showing that the algorithm is more effective; on average, it reaches 99 emails evaluated in up to 150 executions, unlike the 97 obtained with JFLAP. In addition, when evaluating the 100 valid emails between 30, 50, 70, 90, and 110 executions, the algorithm has the highest accuracy, unlike the program with its grammar rules, although the former does not reach the full number of emails.

Figure 11: Results of (number of executions vs. validated emails)

For the case with only 100 valid emails, it can be stated that the algorithm tends to be more efficient JFLAP; as the number of executions increases, it shows some differences with respect to the latter, whose trend line is not so steep. By comparing the equations generated by both cases, for every 20 executions, it can be expected that, on average, the truly valid emails tend to decrease, albeit not so periodically. This is because, for the algorithm, their number is greater. The variability percentage is 85% for the algorithm and 58% for JFLAP. These results could have been generated by the resources of the test device or with the load that represents the multiple executions. The behavior of JFLAP shows a slight increase towards the end, unlike the library. Fig. 12 depicts the results and the equations. The opposite occurs with invalid emails: both had a different behavior because the algorithm tends to improve its results, as seen from the linear trend line. The accuracy of the algorithm is closer to zero, unlike JFLAP. The percentage of variability is 91% for JFLAP and 59% for the algorithm, since the data are less dispersed in the former than in the latter, which shows changes in the results between 50 and 90 executions. In this case, the library has better detection capabilities than JFLAP (Fig. 13).

Figure 12: Valid emails for JFLAP and the library

Figure 13: Invalid emails for JFLAP and the library