1 Introduction
The language Hindavi has its origin in Khariboli dialect. An Urdu invariant of Hindavi came into existence during the Muslim rule from 1206 AD to 1858 AD (Khan Reference Khan2006). The Muslims used Persian/Urdu script for Urdu in contrast with the Devanagari script for Hindavi. Both Urdu and Hindavi (Hindi) are almost same in structure and vocabulary, but Urdu became a literary language after the production of an increasing bulk of the literature during the eighteenth and the nineteenth century (McLane Reference McLane1970). Urdu/Hindi is the national language of Pakistan and an official language in India. According to a report by SIL Ethnologue (Lewis Reference Lewis, Simons and Fennig2013), Urdu/Hindi has 456.2 million speakers in the whole world. Urdu is an under-resourced language and is in need of a number of resources to remain alive in the computational literary world.
State-of-the-art parsing systems are based on treebank grammars but unfortunately, for both, constituency and dependency parsing, treebank based techniques are suffering in case of morphologically rich languages (MRLs) such as Czech (Collins et al. Reference Collins, Ramshaw, Hajič and Tillmann1999), German (Dubey and Keller Reference Dubey and Keller2003), Italian (Corazza et al. Reference Corazza, Lavelli, Satta and Zanoli2004), French (Arun and Keller Reference Arun and Keller2005), Modern Standard Arabic (Kulick et al. Reference Kulick, Gabbard, Marcus, Hajič and Nivre2006), Modern Hebrew (Tsarfaty and Sima’an Reference Tsarfaty and Sima’an2007) and many others (Tsarfaty et al. Reference Tsarfaty, Seddah, Goldberg, Kuebler, Candito, Foster, Versley, Rehbein and Tounsi2010; Abbas Reference Abbas2014b). The data driven parsing models used for dependency parsing are not guaranteed to observe all morphological variants of word form. Efficient parsing results for MRLs are hard to achieve without explicit encoding of linguistic information (Tsarfaty et al. Reference Tsarfaty, Seddah, Kübler and Nivre2013; Abbas Reference Abbas2014b).
Getting state-of-the-art parsing results for an MRL is a challenge till date. According to Tsarfaty et al. (Reference Tsarfaty, Seddah, Goldberg, Kuebler, Candito, Foster, Versley, Rehbein and Tounsi2010, Reference Tsarfaty, Seddah, Kübler and Nivre2013), without proper handling of morphological entities in sentences, promising results for MRLs cannot be achieved. To overcome this problem, one approach is to embed solutions in a parser in the form of morphological component for segmentation and a syntactic component for parsing. A parser generates a formal output by looking at the events in data after assuming independence between the events. Complex morpho-syntactic interactions among events may impose constraints, which lead to explicit encoding of morphological information at the syntactic level. Assigning a correct morphological signature to each word in the presence of extreme data sparseness is almost impossible, due to which this solution is suffering. However, in the other state-of-the-art approach, the best broad coverage and robust parsers available to date have grammars extracted from treebanks, which are a collection of syntactically annotated sentences by humans. In these treebanks, the depth of information encoded in their annotation positively correlates with the parsing performance (Tsarfaty et al. Reference Tsarfaty, Seddah, Kübler and Nivre2013). However, the languages lying in the category of MRLs are not a single homogenous class of languages due to their own cross lingual-variations such as the extent of morphology, flexible ordering, syncretism, fine-grained and unambiguous morphological markers, etc.
Tsarfaty et al. (Reference Tsarfaty, Seddah, Goldberg, Kuebler, Candito, Foster, Versley, Rehbein and Tounsi2010) discussed issues related to encoding of morphological information and the annotation schemes to be adopted for MRLs. These issues highly advocate the need of treebanks annotated with sufficient morphological information. To fulfill this purpose, a treebank for Urdu called the URDU.KON-TB treebank with sufficient information encoded at morphological, part of speech (POS), syntactic and functional level was constructed by Abbas (Reference Abbas2012). The reliability of the treebank annotation scheme can be evaluated manually and automatically. For manual evaluation of the URDU.KON-TB treebank, a statistical evaluation of this treebank (the URDU.KON-TB treebank) was performed through annotated data of annotators (Abbas Reference Abbas2014a; 2014c), through which it was concluded that the annotation scheme is reliable, but the answer of a question that the treebank is suitable for machine learning (ML) was not searched at that time and can be computed through automatic parsing. To achieve this objective, an automated evaluation of the treebank through parser is attempted. Successively, a parser is developed, provided with a grammar. This context free grammar (CFG) is extracted from the URDU.KON-TB treebank computationally. The development procedure and the depth of encoded information in the grammar is presented in Section 3.
Extracted grammar mentioned above is then given to an extended dynamic programming parsing-model which is known as the Earley algorithm (Earley Reference Earley1970). The extensions made to the Earley’s algorithm are given in Section 4. This algorithm is language independent and is capable to parse MRLs like the Cocke–Younger–Kasami (CYK) algorithm as advocated in Tsarfaty et al. (Reference Tsarfaty, Seddah, Kübler and Nivre2013) and Abbas et al. (Reference Abbas, Karamat and Niazi2009). The reason that the Earley’s algorithm was adopted instead of the CYK algorithm is that the CYK takes grammar in Chomsky normal form (CNF) and produces parse trees in the same form or binary trees, while the Earley algorithm does not need a special form of grammar and produces parse trees in any form, hence well suited to treebank based grammars e.g, a CFG. A Chomsky normal form can be converted into a CFG computationally if the CYK algorithm is desired to be used but a model (Earley algorithm) with less issues was adopted because more issues in addition to conversion (if CYK would become the choice at that time) were expected during development as discussed in Section 4.1. Grammar extracted from the URDU.KON-TB treebank is in the form of CFG, so it was better to use the Earley algorithm directly rather than the CYK algorithm (after conversion of extracted CFG into Chomsky normal form). Both algorithms have the same time complexity O(n 3). This O(n 3) time complexity is only the upper bound of the Earley algorithm and it performs better than the CYK algorithms on some grammars in O(n 2) time (Hopcroft et al. Reference Hopcroft, Motwani and Ullman2001). Similarly, the space complexity of CYK algorithm is O(n 2), while the Earley algorithm has the O(n) space complexity (Earley Reference Earley1970). Despite this, both algorithms are competitors of each other (Sikkel and Nijholt Reference Sikkel and Nijholt1997) and both can be used in accordance with the needs.
The related work of parsers development in the domain of Urdu/Hindi language is presented shortly in Section 2 along with their designs and techniques, which set a path toward the construction of a state-of-the-art Urdu parser. Before the construction of the Urdu parser, the preliminary work needed is presented in Section 3, which includes the description of the URDU.KON-TB treebank (Section 3.1) and how the linguistically rich CFG is extracted from this treebank computationally (Section 3.2). To see the reliability of the URDU.KON-TB treebank for machine learning, an Urdu parser was constructed and its algorithmic design has been described in Section 4. The issues removed from the Earley algorithm to improve accuracy and the extensions applied to transform the Earley recognizer to Urdu parser are presented in Section 4.1. After which a run example of the Urdu parser is discussed in Section 5. By applying a sufficiently rich grammar along with the extended parsing model, promising results are obtained and discussed in Section 6. The section initially describes the training and test data and then the Urdu parser results are evaluated through PARSEVAL measure. Finally, the comparison of results with other parsers is presented in the end of this Section 6. Section 7 concludes the work of Urdu parser having morphologically rich grammar with future directions. This parser can help linguists analyze the Urdu sentences computationally and it can be useful in Urdu language processing (ULP) and machine learning domains. By using this parser, the size of the treebank can also be increased. This can be done after getting partial parsed trees of unknown sentences. These partial parsed trees can be corrected and then imported into the URDU.KON-TB treebank. Using this methodology, one can speedily increase the size of a treebank.
2 Related work
As for as the works related to the Urdu parser development are concerned, the first attempt was made in the ParGramFootnote 1 project by Butt and King (Reference Butt, King, Takenobu and Huang2007) using an lexical functional grammar (LFG) framework, then a two stage constraint based dependency parser (CBP) for Hindi was introduced by Bharati et al. (Reference Bharati, Husain, Sharma and Sangal2008). Similarly, the NU-FAST treebank based grammar was used to parse the Urdu sentences using a built-in Prolog parser by Abbas et al. (Reference Abbas, Karamat and Niazi2009) and then a dependency based parser was developed by Bharati et al. (Reference Bharati, Gupta, Yadav, Gali and Sharma2009) for Hindi. Later, a dependency parser for Urdu was tried by Ali and Hussain (Reference Ali and Hussain2010) using MaltParser (Nivre et al. Reference Nivre, Hall, Nilsson, Chanev, Eryigit, Kübler, Marinov and Marsi2007). Similarly, some experiments on dependency parsing for Urdu were performed by Bhat et al. (Reference Bhat, Jain and Sharma2012) using MaltParser and minimum-spanning tree (MST; McDonald et al. Reference McDonald, Pereira, Ribarov and Hajič2005) parsers. In the same year, an Urdu probabilistic parser, using shift-reduce algorithm, was developed by Mukhtar et al. (Reference Mukhtar, Khan, Zuhra and Chiragh2012).
In the Urdu ParGram project (Butt and King Reference Butt, King, Takenobu and Huang2007), the XLEFootnote 2 parser has been used. The encoding of lexical functional grammar in XLE interface is not a simple task. The persons having expertise in theoretical linguistics can only be able to encode such a grammar. The team of the ParGram project made a tremendous effort in this regard. The project of Urdu lexical functional grammar development is in progress and the grammar evaluation results are not yet available.
A two stage dependency parser for Hindi by Bharati et al. (Reference Bharati, Husain, Sharma and Sangal2008) was trained on the Hindi treebank (Begum et al. Reference Begum, Husain, Dhwaj, Sharma, Bai and Sangal2008), which was annotated according to the Paninian grammatical model (Begum et al. Reference Begum, Husain, Dhwaj, Sharma, Bai and Sangal2008). The annotation scheme was designed on the basis of chunks, intra-chunks and karakasFootnote 3 . The scheme adopted in Begum et al. (Reference Begum, Husain, Dhwaj, Sharma, Bai and Sangal2008) of dependency structure (DS) is different from the annotation scheme of phrase structure (PS) and the hyper dependency structure (HDS) of the URDU.KON-TB treebank (Abbas Reference Abbas2012) along with the different data sets used. In comparison to phrase/constituent structure, the DS lacks in information at non-terminal nodes (Bharati et al. Reference Bharati, Husain, Sharma and Sangal2008) and often the information at POS level. This information can be provided at dependency annotation but people are stick to the standard norms. The example of PS and DS is discussed next along with the Figure 1. The Hindi treebank is rich in functional information as compared to morphological, POS and syntactical information. Due to differences in designs of the two stage dependency parser for Hindi and the Urdu parser, only the results are compared, which are presented in Section 6.
Phrase and dependency structure example.
PS and DS are the two traditional annotation structures for treebank annotation. A simple but large difference between phrase and dependency annotation structure is that in PS annotation, the nodes represent phrases or constituents only e.g. a noun phrase (NP) and a verb phrase (VP) as shown in Figure 1(a) for a sentence Michael loves Sara, while in a DS, the nodes represent head words (with or without its syntactic tag) of its dependent words as shown in Figure 1(b) for the same sentence. The PS annotation was first introduced by Chomsky (Reference Chomsky1956) and its main focus is on building small simple constituents or phrases from the words of a sentence as shown in Figure 1(a). The DS annotation has its focus on building relations between the head word and its dependents. It was first proposed by Tesnière. After his death, this theory of DS was presented in Tesnière and Fourquet (Reference Tesnière and Fourquet1959). In the beginning, there was no information coded to the DS as depicted in Figure 1(b) but later on the syntactic annotation became the part of DS presented in Figure 1(c). Further information like POS can be the part of DS annotation shown in Figure 1(d).
The Prolog parser used for evaluation of the NU-FAST treebank (Abbas et al. Reference Abbas, Karamat and Niazi2009) was in fact not the case of parser development, which means that a built-in utility in the inference engine of Prolog was used to parse the sentences. This utility can only be used if you have a definite clause grammar (DCG) or probabilistic definite clause grammar (PDCG). A CFG was extracted computationally through the NU-FAST treebank and then probabilities of grammar rules were counted. Through this process, a probabilistic context free grammar (PCFG) was obtained, which was converted into a probabilistic definite clause grammar format computationally. This probabilistic definite clause grammar was then given to the built-in utility of Prolog inference engine, which is basically a built-in Prolog parser to parse natural languages. Basically, parser was not developed but a built-in parser was used, which concludes that the work is not an algorithmic development of parser that can be compared as explicitly mentioned in Abbas et al. (Reference Abbas, Karamat and Niazi2009).
A simple dependency parser for Hindi was developed by Bharati et al. (Reference Bharati, Gupta, Yadav, Gali and Sharma2009). The parser used a grammar-oriented approach, which was designed on the basis of Paninian grammatical model (Bharati et al. Reference Bharati, Chaitanya, Sangal and Ramakrishnamacharyulu1995; Begum et al. Reference Begum, Husain, Dhwaj, Sharma, Bai and Sangal2008) discussed earlier. The differences between the two stage dependency parser for Hindi (Bharati et al. Reference Bharati, Husain, Sharma and Sangal2008) and the Urdu parser presented earlier are also applied in the case of the simple dependency parser. Due to which only performance results can be compared but not the designs. The maximum results reported in labeled-attachment recall were 65.4% and 58.2% for chunks and intra-chunks, respectively. An average recall of karakas is calculated as 46.67%. A comparative study has been performed and presented in Section 6.
Ali and Hussain used the MaltParser with its default settings in Urdu dependency parser (Ali and Hussain Reference Ali and Hussain2010). When somebody performs experiments with MaltParser with its default settings then such evaluation results are advised not to be compared according to MaltParser license.Footnote 4 The same exercise for parsing Hindi was performed by Agrawal et al. (Reference Agrawal, Agarwal, Husain and Sharma2013), but it was clearly mentioned in the work that MaltParser was being used for error detection in the annotation of Hindi/Urdu treebank (HUTB).Footnote 5 Similarly, the Urdu sentences were parsed by Bhat et al. (Reference Bhat, Jain and Sharma2012) using the same MaltParser. The experiments were performed to identify the parsing issues of Urdu and a development of parser was not claimed, neither it is the case of parser development. Moreover, the data-driven systems are highly criticized on a given set of annotated corpus because these systems are not able to observe all morphological variants of a word form from it (Tsarfaty et al. Reference Tsarfaty, Seddah, Kübler and Nivre2013).
A multi-path shift-reduce parsing algorithm was proposed by Jiang et al. (Reference Jiang, Xiong and Liu2009) for Chinese. Later, this algorithm was used for Urdu parsing by Mukhtar et al. (Reference Mukhtar, Khan, Zuhra and Chiragh2012). A probabilistic context free grammar developed by Mukhtar et al. (Reference Mukhtar, Khan and Zuhra2011) was given to the multi-path shift-reduce Urdu parsing model. It takes a POS tagged sentence as input. A stack and a queue are initialized with a null and a tagged word sequence, respectively and then this initialization ini is stored in an array V. The total bunches of transitions are 2|x| − 1 for which a step loop executes. A state loop runs for each state in V. This loop contains another action loop that decides about shift or reduce action to be taken on each state. After applying the action on a state, it is stored in a next variable which is then recorded in a buffer BUF. When the state loop ends, the BUF contains all constructed states in it. From which K best states are stored further in an array V. The step loop continues and the whole process is repeated until it terminates. Finally, a tree is derived from the best available states in V and displayed accordingly.
A multi-path shift-reduce parser (MPSRP) for Urdu has some limitations. It takes a tagged sentence as input and is not able to parse sentences without POS tagging. The stack used has a fixed memory size, which is not reliable and it can overflow during parsing of long sentences. A probabilistic context free grammar used in this parsing model is ambiguous (Mukhtar et al. Reference Mukhtar, Khan and Zuhra2012). Both the fixed memory size and ambiguous grammar can resist the parsing of long sentences, that is why the parser could not parse sentences with length more than ten words (Mukhtar et al. Reference Mukhtar, Khan, Zuhra and Chiragh2012). The results were not evaluated properly by using some measure e.g. PARSEVAL. A number of seventy-four sentences having length not more than ten words were parsed successfully from 100 sentences, which were then quoted as a 74% of accuracy. The raw corpus used in the development of the parser is partially same as compared to the Urdu parser (Section 4). A comparative study made is detailed in Section 6.
3 Preliminary work
This section describes the preliminary work needed to parse the Urdu sentences through the parser discussed in Section 4. Section 3.1 describes the URDU.KON-TB treebank briefly to give an idea of its annotation scheme, which has a rich morphological, POS, syntactical and functional information. A CFG is then extracted from this treebank presented in Section 3.2.
3.1 The URDU.KON-TB treebank description
A treebank having the PS and the hyper dependency structure annotation with rich information is described in Abbas (Reference Abbas2012). This URDU.KON-TB treebank is used for the training of the Urdu parser discussed in Section 4. The URDU.KON-TB treebank has a semi-semantic POS (SSP) tag set, a semi-semantic syntactic (SSS) tag set and a functional (F) tag set. Morphological information in the labeling of the parser’s lexicon is contained in the SSP tag set of the URDU.KON-TB treebank. A detailed discussion can be seen in Abbas (Reference Abbas2012), however, a short overview is presented here for ease of comprehension.
The SSP tag set hierarchy has twenty-two main tag categories which are divided into sub-categories based on morphology and semantics. In Figure 2, an example of only a verb V is given. A dot ‘.’ symbol is used for the representation of morphology and semantics at the POS level. In Figure 2, the hierarchy of tag labels for the verb V is divided into three levels of depth. The first level contains only one label to distinguish a verb V from other POS labels. The second level contains eleven subcategories of V to represent different morphological or functional forms e.g. V.COP (V as a copula verb (Abbas and Raza Reference Abbas and Raza2014)), V.IMPERF (V has an imperfective form (Butt and Ramchand Reference Butt, Ramchand, Liakata, Jensen and Maillat2001; Butt and Rizvi Reference Butt, Rizvi, Cabredo-Hofherr and Laca2010)), V.INF (V has an infinitive form Butt (Reference Butt and Kachru1993); Abbas and Nabi Khan (Reference Abbas and Nabi Khan2009); Abbas et al. (Reference Abbas, Zia and Khan2015)), etc. The third level contains further twenty-five subcategories to represent the morphological information in depth e.g. V.COP.IMPERF (copula verb has an imperfective form), V.COP.PERF (copula verb has a perfective form), V.COP.ROOT (copula verb has a ROOT form), V.COP.PAST (copula verb has a past tense), V.LIGHT.PAST (light verb has a past tense (Butt Reference Butt2003, Reference Butt, Amberber, Harvey and Baker2010)), etc. These types of combinations are also possible in case of an auxiliary verb as described in Abbas (Reference Abbas2012). This short discussion is about the idea of morphological and verb-functional information encoded at the POS level. This lexical information can be passed up to the syntactical level because the lexical items have some relationship with the other lexical items in a sentence. We will explain it after presenting a short overview of the SSS and F tag set hierarchy.
A verb V example from the URDU.KON-TB treebank.
The SSS and F tag sets contain twenty-six and eighteen tag categories, respectively. The SSS tag set hierarchy is divided into three more levels known as a hierarchical design. An example of a simple noun phrase (NP) is depicted in Figure 3. This is taken from the SSS tag set discussed in Abbas (Reference Abbas2012). A NP is divided into four levels of depth, as in the case of V. The first level is divided into nine subcategories e.g. NP.ACC (accusative case of NP), NP.DAT (dative case of NP), NP-MNR (NP having a manner concept in it), NP.NOM (nominative case of NP), etc. The features are separated by dot ‘.’ and dash ‘-’. In SSS annotation, ‘.’ is used for representing syntactical features while the ‘-’ is used for annotating semantic/functional features. The nine subcategories at the second level of NP annotation are further divided into nineteen subcategories e.g. NP.ACC-OBJ (accusative case of NP acting as a direct object of a sentence), NP.ACC-SUB (accusative case of NP acting as a subject in a sentence), NP.DAT-OBJ2 (dative case of NP acting as an indirect object in a sentence), etc. At the last hierarchical level of the NP, NP.NOM-MNR, NP.NOM-SPT and NP.NOM-TMP are divided into two, three and four subcategories e.g. NP.NOM-MNR-OBJ (NP with nominative case having a concept of manner is acting as a direct object of the sentence), NP.NOM-SPT-OBJ (NP with nominative case having a spatial sense acting as a direct object in a sentence), NP.NOM-TMP-PLINK (NP with nominative case having a temporal sense acting as a predicate link of a sentence), etc.
-
(1)
A noun phrase (NP) example from the URDU.KON-TB treebank.
After presenting the SSP and SSS, we can now understand the passing of lexical information up to the syntactical level. Two sentences with respective trees are given in Example 1 and Figure 4. Between these two sentences, the difference is only the presence of case marker kO. The passing up of lexical information at the POS to the syntactic level can be seen in the two different respective trees. In case of object marking as in Figure 4(a), the case marker (CM) kO with a personal pronoun (P.PERS) us ‘him’ is physically absent and the phrase contains only an inflectional form of personal pronoun as usE ‘him’ concluding a NP. This inflectional form has a hidden sense of CM kO, identifying an accusative case of direct object as NP.ACC-OBJ. On the other hand, the Figure 4(b) contains a CM preceded by a P.PERS. The physical existence of CM concludes a case phrase (KP) rather than a NP and disambiguating the trees as well. In the case of oblique OBL argument, the phrase jangal/N.SPT sE/CM ‘through/from the forest’ is annotated with KP due to instrumental case marker CM in both the trees. The instrumental INST semantic property of the CM is added up to the KP and similarly the word jangal ‘forest’ is a spatial noun whose spatial SPT semantic property is passed up to KP in order, which is acting as an oblique argument OBL in the sentence. The purpose of such information at morphological, POS, syntactical and functional level of annotation is not only to disambiguate the parse trees but it is essential to parse MRLs as concluded by Tsarfaty et al. (Reference Tsarfaty, Seddah, Kübler and Nivre2013).
Passing up lexical information to the syntactical level.
3.2 Grammar extraction
The URDU.KON-TB treebank is a manually annotated set of 1,400 parsed sentences, which is recorded in a text file on a computer in the form of 1,400 bracketed sentences. Initial twenty bracketed sentences from each 100 are separated in another text file concluding 280 sentences, which are then used for the development of a test suite. The test suite is further divided into two halves representing test data and held out data resulting in 140 sentences in each half. The held out data was used in the development of the Urdu parser, while the test data was used for evaluation of results after the completion of the Urdu parser. From the first residual text file with 1,120 bracketed sentences, a CFG was extracted using a stack based extraction module given in Algorithm 1. The text file contained bracketed sentences (displayed in Figure 5) separated with a ‘$’ sign and is given as an input file to the algorithm. The algorithm used a Stack and a StrArray to process the productions between the left and the right parenthesis e.g. ‘(’ and ‘)’ of bracketed sentences. For example, If there is a production like ( NP ( N.SPT gHar )), then the algorithm pushes all the strings one-by-one on to the Stack as ( NP ( N.SPT gHar until a first right parenthesis ‘)’ after a token gHar ‘house’ is introduced. Without storing ‘)’ on the Stack, already pushed strings are popped back until a left parenthesis ‘(’ comes before the POS tag N.SPT and is stored respectively in an array StrArray in reverse order as gHar N.SPT without ‘(’. At this point, a production/rule extraction has been completed in StrArray. The last element N.SPT of StrArray is copied back at the top of the Stack for further usage, because it is the part of the next production to be extracted. The StrArray elements are recorded in an output file in its original order using lines twenty-four to thirty-three of the algorithm concluding a production as N.SPT → gHar. After making the StrArray empty, reading of the strings from the input file remains continued. As the ‘)’ appears, the popping back process from the Stack starts and the new production arrives in the StrArray as N.SPT NP, which is then re-ordered as NP → N.SPT. This whole process continues until the end of file and finally an output file with a complete CFG productions of 1,120 bracketed sentences is obtained. The extracted CFG is then processed by the Urdu parser to obtain a CFG database having unique productions from it. During this process, the labeling as L and NL at the end of each production is done. The productions having only lexical items at their right-hand side are labeled as L and the productions which have non-lexical items on their right-hand side are labeled as NL. The purpose of this labeling is to provide an already processed mechanism through which the parsing algorithm can identify a production as L type or NL type speedily without checking it thoroughly. This identification also helps the PREDICTOR(), COMPLETER() or SCANNER() of the Urdu parser to process further. A CFG is depicted in Figure 6 for the example sentence in 2.
Bracketed annotation of Example 2.
A CFG of the example sentence in 2.
A CFG extraction algorithm
-
(2)
4 Urdu parser
Without handling the issues discussed in Section 4.1, the Earley’s algorithm was not able to provide state-of-the-art evaluation results for Urdu. These issues caused the parsing discontinuities or the parsing failures (the parser failed to parse next during processing of a grammar production), due to which modifications or extensions were applied on the basic algorithm to remove these parsing anomalies. The extended version is depicted in Algorithm 2. In this algorithm, the extracted CFG given as a database has three fields/columns in the form of LHS (Left-Hand Side of production), RHS (Right-Hand Side of production) and Type (Type of production either L or NL), which can be inferred through matching with the CFG in Figure 6. After taking a sentence as input, various variables are initialized along with a chart[] array, which is an array of objects. The starting value of the chart is given as ROOT @ S. In place of bullet/dot symbol ‘•’ used in the Earley algorithm, here an ‘@’ symbol is used because the bullet/dot symbol is extensively used in the hierarchical annotation of the URDU.KON-TB treebank, from which the grammar productions are extracted. The working of the algorithm is similar to the Earley’s algorithm except modifications in the PREDICTOR(), COMPLETER() and a SCANNER() along with the additional functions i.e. an EDITOR() for an automatic editing of discontinuous parses and a BUILDER() for building parse trees presented at the end of the algorithm.
Urdu Parser
Before the execution of the internal loop, the scannerFlag is set to false (which is dealt within the scanner Algorithm 4) and an initial state of the chart is printed. Within the internal loop, the productions inserted in the respective charts are picked up one-by-one and are split with space to find the next processing non-terminal in tempString and its location index. If the tempString is found to be empty then the COMPLETER() will execute to complete the status of the relevant production by moving forward the ‘@’ symbol, which is discussed in Section 4.1.7 along with its Algorithm 9. Otherwise, there are two possibilities, which are decided on the basis of further productions extracted from the grammar database into a record set rs. The first possibility of PREDICTOR() will execute if the value of rs is true, which means that it will contain further extracted productions and then the PREDICTOR() will add predicted productions into the current chart, whose further detail is presented in Section 4.1.1 with the Algorithm 3. Similarly, the second possibility of SCANNER() will execute if rs is found to be empty and then SCANNER() will create a new chart and it will then add a relevant L type production into this chart from a previous chart as illustrated in Section 4.1.2 along with its Algorithm 4.
Predictor
Scanner
During processing of COMPLETER(), PREDICTOR() and SCANNER(), parsing discontinuities can happen. To check these types of phenomena, an EDITOR() will come into action and it will remove all previous irrelevant entries and charts causing discontinuity up to an optimal point of parsing discovered earlier. The detailed discussion is presented in Section 4.1.6 along with its Algorithm 8. After the end of the external loop, the parsed solutions are generated and stored in the form of charts with entries, but not in the form of parsed trees. To represent parsed solutions in the form of bracketed parsed trees, a BUILDER() function is executed. This constructs parsed trees of solutions by manipulating the back-pointers calculated in COMPLETER() function. The BUILDER() is able to display all parsed solutions of a given sentence as discussed in Section 4.1.4 along with its relevant Algorithm 6, then the Algorithm 2 for the Urdu parserFootnote 6 is exited with complete generation of charts and bracketed parsed trees. The discussion of this main Algorithm 2 is done in this section, while the algorithms of functions called by the main algorithm are discussed in detail in the respective subsections of Section 4.1.
4.1 Extended functions
Functions called by the main Algorithm 2 are extended/introduced to meet the parsing requirement of MRL Urdu. These functions mainly include the PREDICTOR(), COMPLETER(), SCANNER(), EDITOR(), BUILDER()| and the BACKPOINTER(). The discussion of each function algorithm along with the issues is presented as follows.
4.1.1 Eliminating useless predictions
Earley’s Predictor() adds useless productions in charts which cause a wastage of time during processing, and increase the chance of misleading direction toward a wrong solution or discontinuous parse if these useless productions are selected by the Earley’s Completer() or Earley’s Scanner() for further processing. Suppose, the current token to be parsed in an input sentence is
‘Khan’, which is a proper noun and there is a NL type production NP → @ N.PROP N.PROP residing in the current chart of the parser. Here, NP is the noun phrase, N.PROP is the proper noun and the ‘@’ symbol is the equivalent of the bullet/dot • symbol of the Earley algorithm. The ‘@’ symbol before a non-terminal on the RHS of the production is the case of predictor and the non-extended PREDICTOR() adds all the available L type productions of N.PROP into the chart along with the relevant production N.PROP → @
from the grammar. Even the addition of irrelevant productions are not required, only the relevant production N.PROP → @
has to be added in the chart. This addition of irrelevant/useless productions is also true for other lexical items e.g. adjectives, personal pronouns, case markers, etc. These useless additions cause a wastage of time and increase the chance of misleading direction toward a wrong solution or a discontinuous parse/state. To resolve this issue, the PREDICTOR() is extended to abandon the selection and insertion of useless productions from the grammar into the charts as given in Algorithm 3 and its execution is discussed next.
When the main parsing Algorithm 2 calls the PREDICTOR(), then it checks the type of production first either as NL or L using an external if condition. For both types, it finds the existence of predicted production in current chart chart[i] using a for loop controlled by the size of the current chart chartSize[i]. This loop from line three to eight is for NL type of productions and from line eighteen to twenty-three is for L type of productions. The loop will break if the predicted production is located in chart[i] and then it will be the case when there is no need to add this production into the chart. However, if it becomes unable to locate the predicted production then the value of k becomes equal to chartSize[i] and if it happens, then a repeat-until loop is used to add all extracted predicted-productions into the chart[i]. In Earley’s algorithm, this process is same for both NL and L types productions, which causes the addition of irrelevant productions. To make it more accurate, the PREDICTOR() is divided into two halves to deal with NL and L type productions separately. In dealing with L type of productions, the PREDICTOR() is introduced with another condition displayed at line twenty-six of Algorithm 3, which enforces the predictor to add only relevant productions into the chart. It matches the token at RHS of predicted-production rs.getString(2) with the current token Sentence[i] in a given input sentence. This condition forces the PREDICTOR() to introduce only the relevant productions in charts and eliminates the limited possibility of misleading direction toward a wrong solution or a discontinuous parse. After removal of irrelevant productions, the wastage-time factor is reduced to optimal linear-time O(n), which at least is required for processing of n number of tokens in a given input sentence.
4.1.2 Extended scanner
In Earley’s parsing algorithm, the scanner() only matches the RHS of the L type production with the current token in a given sentence and may cause a wrong selection with an incorrect POS tag at the LHS of this L type production. For example, the verb
‘is’ has different tags in the grammar. It can act as an auxiliary in a sentence with present tense e.g VAUX.PRES →
. It can behave as a copula verb e.g. V.COP.PRES →
and it can also act as a main verb e.g. V.PRES →
. This concept of having more than one tag is true for other lexical items as well. So, if this L type production VAUX.PRES → @
is the right candidate in the current chart then the scanner() of the Earley algorithm can select other available productions from the grammar due to a check on the RHS only. This can cause the wrong solution or a discontinuous/failed state in the chart during parsing. To remove this issue, the scanner() is extended in the same way as was done with the PREDICTOR() in Section 4. This solution presented in Algorithm 4 solves the issue partially at this level, but it is completed in Section 4.1.6.
When the SCANNER() is called, it extracts all relevant L type productions from grammar after matching their LHS and RHS with currentRule[index - 1] and tempString of current L type production in a chart, respectively. It adds the correct L type production in a new chart chart[i + 1] after checking three conditions. At first, it checks that the chart number is not exceeding the length of the sentence, as the total number of charts to be produced should be equal to LENGTH(Sentence)+1. Secondly, it checks that the token tempString in the current processing L type production is equal to the current token Sentence[i] in a given sentence. After that if the scannerFlag is false, then the new entry of matched L type production is added into the new chart. During this process, the scannerFlag is set to true value along with a record of some variables fi, fj, fid, which will be used in EDITOR() presented in Algorithm 8. By introducing this modification, the possibility of wrong selection of production from the grammar is abandoned and the exactly matched L type production extracted from the grammar is added to the next chart accordingly. An issue left in this solution is that the Earley’s PREDICTOR can add all the L type productions mentioned in Section 4 into the current chart for processing of scanner(). In this situation, the scanner() will not know which one is the true candidate production for parsing. This issue is addressed and resolved in Section 4.1.6.
4.1.3 Back-pointers calculation
Earley parsing algorithm is a generator or a recognizer and hence, cannot produce parse trees or bracketed trees. The output of the Earley algorithm is the N+1 number of charts where N is the number of words in a given sentence. To produce parse trees or bracketed trees from the output of the Earley algorithm, an idea of back-pointers was shortly discussed by Earley (Reference Earley1968) in his doctoral thesis. The same idea is implemented in detail to produce parse trees in our Urdu parser. To understand the calculation of back-pointers, a sentence given in Example 3 is parsed from the Urdu parser. The charts generated through it are depicted in Figure 7. Only relevant states are displayed as can be inferred from the non-sequential values of STATEID column. The column DOT-POSITION is basically the position of ‘@’ in productions.
-
(3)
A back-pointer calculation example of the Urdu parser.
The COMPLETER()
Algorithm 9 calls the BACKPOINTER()
Algorithm 5 to calculate the values of back-pointers. For example, during processing of STATEID 3 in chart 1 of Figure 7, the COMPLETER() calls the BACKPOINTER() with string type arguments previousRule and dummy@Position as KP.POSS → P.PERS @ CM and ‘0,1’, respectively. The final indexed value of ‘@’ in variable tempIndex after subtraction obtained through the previousRule is 1. The string value P.PERS at this index is then stored in a variable NT. The value of k becomes 0 at this stage in the algorithm. The external loop is used to traverse the charts one-by-one from the recent state of the chart. After checking the condition of tempIndex at line eight, another loop for traversal of chart entries is executed. At this point, a production P.PERS →
@ at state 0 of chart 1 is stored finally in the cRule. The index of ‘@’ here in this production is stored in the tIndex as 2. A condition presented next becomes true and the value of the backPointer is calculated as ‘1-0’. The value in the DOT-POSITION column of this state is split with ‘,’ and stored in a temporary variable dummy@P. Before breaking of internal loop, the values in l, tempIndex and NT are updated with 1, 0 and KP.POSS, respectively. Then the control goes to the external loop in continuity with l=1, but now the condition of tempIndex becomes false and finally the external loop breaks. The calculated ‘1-0’ value of backPointer is then displayed by the COMPLETER() in the relevant state of the chart. The rest of the back-pointers displayed in Figure 7 are calculated in the same way. These back-pointers are further used in building of bracketed parse-trees which will be discussed in Algorithm 6.
Back Pointer
Builder
4.1.4 Building bracketed parse trees
All the back-pointers are calculated and stored in each relevant state of the chart as presented in Section 4.1.3. When all the states in the respective charts are evaluated and the external loop in Algorithm 2 is exited then another function BUILDER() depicted in Algorithm 6 is called. After displaying all chart entries as shown in Figure 7, the possible bracketed parse trees are evaluated and displayed by the BUILDER() function. Both the BUILDER() and the BACKPOINTER() contributes to shift our Algorithm 2 from a generator to a parser in contrast of the Earley’s algorithm.
After displaying the chart entries in Figure 7 for the sentence given in Example 3, the BUILDER() sets the num and chartN to zero and the length of sentence, respectively. A loop is used to calculate the location of all S solution productions in the last chart and stored them in a string list bp[]. After evaluation, it has only one solution production with ‘8-1’ string value in bp[] for the example sentence. A bracketed-tree class type array of objects tree[] is initialized with the number of solutions found at line ten of the algorithm. This tree object is then called a user-defined method named build(bp.get(i), chart) with two arguments in another loop. This method builds an unformatted intermediate bracketed-parse-tree with interlinked back-pointers from chart states and reveals the leaf nodes only as ( 8-1 ( 4-1 ( 2-2 ( 1-0
) ( 2-0
) ) ( 3-0
) ( 4-0
) ) ( 5-1 ( 5-0
) ) ( 6-1 ( 6-0
) ) ( 7-1 ( 7-0
) ) ( 8-0. ) ). This intermediate parse tree can be understood well by looking at the given back-pointers in the respective chart states.
A third independent loop starts and prepares the intermediate parse tree into a complete unformatted parse tree using a statement given as tree[i].prepare(chart). When this loop is exited then the parse tree has obtained a form as ( S ( NP.NOM-SUB ( KP.POSS ( P.PERS
) ( CM
) ) ( N
) ( PT.INTF
) ) ( ADVP-SPT-MODF ( ADV.SPT
) ) ( ADJP-MNR-PLINK ( ADJ.MNR
) ) ( VCMAIN ( V.COP.PRES
) ) ( M.S. ) ). So, this prepare() method only replaces the back-pointer with the LHS of relevant productions. At this point, the only thing left is the formatting of this parse tree, which is done from line seventeen to thirty-five in Algorithm 6 and the parse tree gets a final form as depicted in Figure 8.
An output of the BUILDER() method.
4.1.5 Empty productions
Empty productions are divided into two categories. The first one is related to diacritic productions e.g. DIA → * and the second one is related to non-diacritic productions e.g. P.PERS → *. The POS tags DIA and P.PERS are used to represent diacritics and personal pronouns, respectively, where the ‘*’ is used to represent absence of these categories. The diacritic is a mark or a sign that is placed over, under, or through a letter of a word in some languages to describe that the letter of a word should be pronounced in a particular way or the word with a diacritic at the last letter has some sort of connection to the following word like compound words in Urdu which will be discussed next. As tags to represent these empty productions exist in our grammar, there is a need to deal with it. It can cause discontinuity during parsing because the lexical item may or may not be present for both the categories in a given sentence. A solution was proposed for compilers by Aho et al. (Reference Aho, Lam, Sethi and Ullman2007), Appel and Palsberg (Reference Appel and Palsberg2007) and Leblanc and Fischer (Reference Leblanc and Fischer1988). A similar solution was coded for the Earley algorithm by Aycock and Horspool (Reference Aycock and Horspool2002), which is adopted. The solution is to process the empty productions implicitly in the algorithm by moving the ‘@’ symbol ahead. This solution causes frequent discontinuity during parsing and its property of self-decision at irrelevant places makes the things more worse. It has been found that it does not work well for Urdu.
Usually, diacritics are not present in modern Urdu writing, but the older literature makes extensive use of diacritics e.g. a compound word
AbE h2ayAt ‘The water of life’ with a diacritic at the last letter of the first word Ab ‘water’ making it a possessive entity of the following word h2ayAt ‘life’, a single word
taqrIban ‘almost’ with a diacritic at the end of the last letter allowing this word to be pronounced as taqrIba-n with ‘n’ sound and not as taqrIba. The lexicon can be viewed on the website designed by the Center for Language EngineeringFootnote
7
under the rights protected by the Ministry of Information and Technology, Pakistan.Footnote
8
The diacritic used in the first example under the last letter
b of the first word is called zErE-Iz3Afat (a diacritic for addition), which is connecting the first word with the following word and thus making a compound word. This phenomenon is still in use in modern Urdu writing. The diacritic above the last letter
a in second example is called tanwin (a diacritic for final post-nasalization), which is different from the first example and related to pronunciation of the letter. There are also other diacritics in use as well e.g., zEr, zabar, pEsh, taSdId, etc. In short, the problem of the modern Urdu text is this that diacritics may arise in the text or not.
During parsing, a compound word can come with the diacritic zErE-Iz3Afat in a given sentence e.g.
Sehr makkah ‘The city of Makkah’. This example has two words
Sehr ‘city’ and the
makkah ‘Makkah’, but the diacritic E is absent at the end of the first word Sehr. In such cases, its presence is by default understood by the native speakers. The production exists in the grammar to handle this compound word is NP-SPT → @ N.SPT DIA N.PROP.SPT. When the first word Sehr/N.SPT is processed by the SCANNER() then the ‘@’ is moved ahead and the production becomes NP-SPT → N.SPT @ DIA N.PROP.SPT. The DIA is the candidate to be executed next to represent the absence of diacritic at the end of first word Sehr. The PREDICTOR() deals this DIA empty production implicitly by moving the ‘@’ ahead and adds the updated production NP-SPT → N.SPT DIA @ N.PROP.SPT in the same chart. Similarly, the second word makkah/N.PROP.SPT is processed by the SCANNER() and the production final state becomes like NP-SPT → N.SPT DIA N.PROP.SPT @. The problem with this solution by Aycock and Horspool (Reference Aycock and Horspool2002) is that it performs the implicit transaction silently for both the compound and non-compound words as observed and is unable to differentiate between these type of words. For example, if there is a case of compound word as discussed then the solution is perfect, but in the case of non-compound words if two independent words
gHar ‘The house’ and
makkah ‘Makkah’ appear in a same position like discussed in compound words e.g.
gHar makkah mEN hE ‘The house is in Makkah’, then this solution cannot identify the context and it applies the transaction in the same way due to the same POS tagging of the gHar and the Sehr.
The diacritics are the part of words in Urdu. In the URDU.KON-TB treebank annotation, no tag was used for the presence of diacritics. It is a wonder, why the DIA tag is used to represent absence only. After facing a problem discussed earlier, the production of DIA was removed from a sample of the grammar and achieved quite good results. It is a tested proposal that this production of DIA should be removed to achieve good parsing results on this treebank.
The absence of an argument or an optional lexical item in the sentence is the case of non-diacritic empty production. In this case, the discontinuity rate is less than the other discussed earlier. It may be due to the independent constituency structure of this category. For example, if a subject with nominative case is missing in a given sentence then the grammar has productions as NP.NOM-SUB → P.PERS and P.PERS → *. Both productions have the singletons (one terminal/non-terminal) on their RHS. This property of singletons is also existed for the other empty productions in this category. The constituent structure is different from the category of diacritic productions. It is not sure but it may be the singletons on the RHS, which are preventing this category not to show immaturity during the parsing.
Due to high frequency of the DIA production in the URDU.KON-TB treebank, the proposed solution of Aycock and Horspool (Reference Aycock and Horspool2002) was implemented in PREDICTOR() by replacing the lines eleven and twenty-seven with the Algorithm 7 but the results found were not promising. So, an explicit method to represent empty productions has been adopted. A ‘*’ is usually typed in the given sentence to represent absence of diacritics, arguments, lexical items, etc. Due to this explicit approach, the Urdu parser is jelling with the grammar without any issue related to empty productions.
Empty Productions
4.1.6 Lexical dynamic behavior
The issue is related to the words which are homonyms, homographs, homophones, heteronyms and polysemes. A strict definition is considered to these attributes, that means at least the words have the same spelling. It is considered because the parser matches the tokens with the grammar lexicon or with the current word in a given sentence. The case of homonym words in a strict sense is going to be discussed here and the same concept is applicable on other attributes as well. There was an error in the Earley’s algorithm, which has been removed in the Urdu parser. It was observed that when the Earley Predictor introduced the right candidate word along with some of its homonyms in the current chart and the Earley Scanner started its search for the right candidate word to be processed from the beginning of the current chart, then if homonyms of the right candidate word were present with different POS tags at the earlier positions in the current chart then the Scanner picked it up for processing and added it into the next chart after matching with the current token in the given input sentence. As this homonym had a different POS tag as compared to the right candidate word, so consequently the Completer and the Predictor processed further productions and finally the parser got into a wrong solution or a discontinuous state. This issue is explained with an example as follows.
For example, the word
kI is a homonym in Urdu. It can behave in two ways e.g. a possessive case marker and a verb. Being a possessive case marker, it contains a possessive meaning ‘of’ in 4. On the other hand, it contains a meaning of ‘did’ in 5 as a verb.
-
(4)
-
(5)
In the grammar of the Urdu parser, this word kI has different POS tags, as a case marker CM, a perfective verb V.PERF and a perfective light verb V.LIGHT.PERF. Suppose the word kI actually comes as a V.PERF at the end of a given sentence. For its processing, the Scanner can pick up the wrong choice with the CM or the V.LIGHT.PERF if these choices are available in the current chart at earlier positions as compared to the right choice. Due to this wrong selection, the relevant productions of the verb V.PERF will not be completed in the next chart and the parser will go with the wrong solution or the discontinuous state. To resolve this issue, it is needed to delete all the failed charts and continue the parsing process with the other choice. To address this issue, the Scanner of the Earley algorithm is modified in the Urdu parser as depicted in Algorithm 4, which records the failed state in variables fi = i, fj = j and fid = id. At line twenty-one of Algorithm 2, after checking some conditions, an EDITOR() presented in Algorithm 8 is called by the Urdu parser to heal this discontinuous state.
Editor
When the parser is discontinued at chart[i + 1], then by using recorded variables in SCANNER(), the EDITOR() first deletes and re-initializes the chart[i + 1]. In a sequence, it further deletes and re-initializes the charts from i to fi + 1. fi is basically the chart number, where homonyms are available and fj is the location of that wrong choice e.g. CM →
in a chart. The wrong choice is stored in a rule array after splitting by space. A loop is used to traverse all productions of a chart where the homonyms are available. The chart productions are stored temporarily in a temprule array. When the RHS of both the arrays are found to be equal then the LHS are checked. If LHS are found to be equal then those productions are skipped and recorded otherwise. In this way, the next choice V.PERF →
is located and the ith
and jth
loop variables of the Urdu parser are set to that choice for further processing. Continuing in this way, the parser finally moves toward an optimal solution.
4.1.7 Completer’s limitations
This issue of wrong solution or a discontinuous/failed parse obtained during parsing is related to subordinate clauses, when the number of subordinate clauses in a sentence is more than one. The issue does not appear often and is related to NL type productions, specially the subordinate clauses denoted by SBAR in an annotated or a parsed sentence. The wrong production caused the parsing discontinuity can lie in any chart but one thing is sure that the right choice of production also exists in the same chart but not selected by the Completer due to the order of productions. In the Earley algorithm, after finalizing its choice of production, the Completer never comes back to seek the other choice even made a wrong choice in its first attempt. Due to this restriction, it was observed that the parser produced a discontinuous parse in case of the nested subordinate clauses and the discontinuity occurred during the processing of the last chart when the production of subordinate clause SBAR was being manipulated.
-
(6)
“Due to these conflicts, he could not find an opportunity that he could do the reforms like that as his heart wanted”
A sentence of twenty-three tokens in 6 with two subordinate clauses highlighted with SBAR is also an evidence of this issue among the other examples. After the parsing of productions in the last (twenty-third) chart for this sentence, the order of the complete productions should be as follows. The ‘@’ at the end of each production represents the complete status of productions.
But, unfortunately, the parser went into a discontinuous state without any solution during processing of the last chart with the productions given in Figure 9. This means that the parser did not find a complete solution production ‘S’ with ‘@’ at its end. As it was the last chart processed for the given sentence and another chart could not be added. So, the parser discontinued finally with the incomplete productions in the last chart without any solution.
Incomplete solution of the Urdu paser.
In Figure 9, the parser performed well up to the completion of first SBAR →. . .@ production. Then the COMPLETER() went back in charts to search a related incomplete production with the properties like SBAR on its RHS and the ‘@’ symbol before the SBAR, as @ SBAR. The COMPLETER() made a fault in chart 12 in the presence of a wrong choice with the similar properties at higher precedence. It found an incomplete SBAR production as SBAR → C.SBORD NP.NOM-SUB @ SBAR ADVP-MNR-MODF NP.NOM-MNR-OBJ VCMAIN M.S. As the ‘@’ symbol was before the SBAR, so the COMPLETER() picked it up. After moving the ‘@’ forward, it added the updated production in the last chart as can be seen in Figure 9. The PREDICTOR() then checked the ‘@’ before the ADVP-MNR-MODF and the parser went into a wrong direction. It happened because the COMPLETER() picked up the wrong production in chart 12, even the right choice S → KP-INST-MODF KP.DAT-SUB NP.NOM-OBJ VCMAIN @ SBAR was also there in the early rows of that chart. To resolve this issue, it is needed to allow the COMPLETER() to go back further until a successful parse has been obtained as can be seen in Algorithm 9.
Completer
When the Urdu parser called the COMPLETER(), it first sets the completerCheck flag to false. This is the flag which is used to allow the COMPLETER() to back track the right choice among the NL type productions. The COMPLETER() has two main loops. The external loop is used to handle the previous charts chart[pc] from i − 1 to 0. The internal loop is used to traverse the chart states from 0 to chartSize[pc] − 1. With the execution of internal loop, each candidate chart production chart[pc].getRule(c) is stored first in the previousRule array through the dummyString. An already processed position of the ‘@’ symbol is recorded in the dummy@Position. After getting index of the ‘@’ from the previousRule, a condition is checked that the production in the previousRule is not a complete production. If it is the case, then after matching the LHS of the current chart production currentRule[0] with the non-terminal after the ‘@’ in the previous chart production previousRule.get(pIndex+1), the ‘@’ symbol is moved forward. The updated and formatted previousRule is stored in another array pStr for further processing. The existence of this updated production in chart[i] is checked via a recursion Boolean variable. If the recursion is found to be false then back-pointers are calculated first as explained in Section 4.1.3. After calculating the back-pointers, the updated production entry is then added and printed into a chart[i] by setting the completerCheck to true. After updating some variable, the previousRule is again cleared and the internal loop continues. However, if the previousRule is found to be a complete state, then the array previousRule is made empty and the internal loop continues. At the end of internal loop, there are some conditions which deal with the discontinuity issues of the COMPLETER() discussed in this section. If the completerCheck is found to be true and the chart number is less than the length of the sentence then the external loop breaks, which means that the COMPLETER() has found the solution and there is no need to go back. On the other hand, if the completerCheck is found to be true and the chart number is greater or equal to the length of the sentence then the COMPLETER() is allowed to back track by setting its flag to its default value.
5 A run example
To see the effect of the Urdu parser, we examine Example 7. The length of the sentence is five tokens, for which the parser generates 0 to 5 charts. All irrelevant NL type productions are removed from the output charts to save the document space. Due to this removal, the values in the STATID column of Figure 10 are not consecutive. The charts generated through the parser without the bracketed parse tree are displayed in Figure 10. After displaying these charts, the parser then displays the bracketed parse tree of this sentence, which can be seen in Figure 11.
Charts generated by the Urdu parser for a sentence 7.
A bracketed parse tree generated by the Urdu parser for a sentence 7.
-
(7)
After the removal of issues discussed in Section 4.1, the parser has got the following benefits. The output of the parser is so directed, speedy and refined in the sense that no extra or irrelevant L type productions are introduced by the PREDICTOR(). It is really hard now that the SCANNER() will select a wrong choice of production. If it happens then the SCANNER() has a tendency to correct itself. The COMPLETER() is boosted up to find a solution if the solution is available in any chart at any position. Empty productions are handled but it is better to remove them from the grammar completely. The calculation of back-pointers in the COMPLETER() is helpful to the BUILDER(), which builds bracketed parse trees of the given sentence. The EDITOR() provides a mechanism through which failed parsed output is edited and corrected. These all features make up an Urdu parser with rich morphological, syntactical and functional information in the form of a grammar in it.
6 Experimentation and results
The URDU.KON-TB treebank contains 1,400 annotated sentences. The sentences are divided into 80% training data (for the development of grammar) and 20% test data (for the development of test suite). First, a CFG is extracted computationally from the training data which is categorized into L and NL type productions. The test data is further divided into 10% held-out data and 10% test data. The held-out data is used in the development of the Urdu parser, while the test data is used for evaluation of results after the completion of the Urdu parser. To make the test data more valuable and reliable for results, ten sentences from each 100 of 1,400 sentences are selected. The test data so contains 140 sentences in all. In the test data, the average length is 13.73 words per sentence, the minimum length of a sentence found is five words and the maximum length of a sentence is forty-six words. All items which can exist in a normal text are considered e.g., punctuation, null elements, diacritics, headings, regard titles, Hadees (statements of the prophets), anaphora within a sentence, and others except the unknownFootnote 9 words which will be dealt statistically when this parser will be shifted toward a probabilistic one.
The PARSEVAL measures are used to evaluate the results of the Urdu parser computationallyFootnote 10 . The evaluation results of the Urdu parser depicted in Table 1 includes the number of sentences in test, gold and matched set, precision and recall percentages, f-score, and crossing brackets. The PARSEVAL measures are calculated in two ways on the basis of constituents and their results are presented in rows as A-1 and T-2. The results in row A-1 of the table are calculated on the average basis and the results in row T-2 are calculated on the basis of totality, which is a standard method of calculation. The results given in Table 1 generally describe that for the Length of a sentence in words, the parser produces a number of constituents in a Test parse. If Test parse contains such number of constituents then such number of constituents are Matched with the constituents available in the Gold data. Precision is calculated by dividing the Matched constituents with the constituents available in the Test parse, while the Recall is calculated by dividing the Matched constituents with the constituents available in the Gold data. The F-score is the harmonic mean of Precision and Recall.
Evaluation results of the Urdu parser
A two stage constraint based dependency parser for Hindi (Bharati et al. Reference Bharati, Husain, Sharma and Sangal2008) was trained on 1,185 sentences from the Hindi treebank (Begum et al. Reference Begum, Husain, Dhwaj, Sharma, Bai and Sangal2008). The test data contained 220 sentences but their average length was not reported. The evaluation results in the form of unlabeled attachment (UA), labeled (L) and labeled attachment (LA) are provided by Bharati et al. (Reference Bharati, Husain, Sharma and Sangal2008). From which only the percentage values for LA can be compared with the results of the Urdu parser because LA counts only the correct number of heads and dependency arcs with its labels. The percentage value of LA reported without recall is 75%. However, the LA with recall (LA-R) percentages are also provided for twelve different labels, whose average is 66.32%. As the LA counts only the correct number of heads and dependency arcs with its labels or constituents produced in the parse, so according to this, the Urdu parser has the constituent accuracy or LA in T-2 as 96.76%Footnote 11 , which is 21.76% better than the two stage Hindi dependency parser. On the other hand, for comparison of the LA-R, we can compare the calculated average percentage 66.32% with the recall value in A-1 of the Table 1 logically, but being on the safe side after comparing this value with the recall percentage in T-2, it can be concluded that the Urdu parser outperforms the two stage Hindi dependency parser with 12.48% in recall.
The Urdu parser outperforms the simple Hindi dependency parser (SP) by Bharati et al. (Reference Bharati, Gupta, Yadav, Gali and Sharma2009) with an additional recall of 22%. In (Bharati et al. Reference Bharati, Gupta, Yadav, Gali and Sharma2009), only precision and recall percentages are given. That is why only the precision and recall percentages of LA are compared. For chunks, intra-chunks and karakas, the precision percentages of LA (LA-P) achieved by the simple Hindi dependency parser are 82.3%, 71.2% and 74.1%, respectively. The average of these LA-P percentages is 75.9%, which is 20.9% less precision than the Urdu parser in row T-2. Similarly, Hindi dependency parser achieved LA recalls in case of chunks, intra-chunks and karakas as 65.4%, 58.2% and 46.7%, respectively. The average of these percentages is calculated as 56.8%, which is now the final LA recall percentage of the Hindi dependency parser. For comparison, the recall percentage of the Urdu parser used is mentioned in row T-2 as 78.8%. The values obtained for both the parsers concludes that the Urdu parser outperforms the simple Hindi dependency parser with 22% increase in recall.
The MPSRP (Mukhtar et al. Reference Mukhtar, Khan, Zuhra and Chiragh2012) for Urdu parsed seventy-four sentences successfully out of 100 and it was then reported as a 74% of accuracy. This evaluation is very weak because the successful parsed sentences were not compared with the gold standard. Recall is a value obtained through dividing the Matched constituents with the constituents available in Gold data. As recall percentage in our case is 78.8%, so we can say that the Urdu parser beats the MPSRP with a 4.8% increase in recall. On the other hand, from the first 100 sentences of the test data, the Urdu parser provides eighty-nine sentences with parsed solutions. Comparatively, the Urdu parser has 15% more accuracy than the MPSRP, but the parsed solutions are not compared with the Gold data. So, by considering the safe side, we can repeat our argument that the Urdu parser beats the MPSRP with a 4.8% increase in recall.
7 Conclusion
To fulfill the encoding requirements of rich information for MRL Urdu, a grammar having rich morphological, POS, syntactical and functional information was extracted from the URDU.KON-TB treebank. The existing dynamic programming algorithm known as the Earley algorithm was extended to accomplish the Urdu parsing needs. Several Urdu parsing issues have been resolved through this extension. After removal of issues, the output of the Urdu parser is so directed, speedy and refined in a sense that no extra or irrelevant L type productions are introduced by the parser. It is really hard now that the Urdu parser will select a wrong choice of production because it has a tendency to correct itself. Urdu parser is boosted up to find a solution if the solution is available in any chart at any position. Empty productions are handled partially. The calculation of back pointers is helpful in building the bracketed parse trees of a given sentence. The parser has a mechanism through which failed parsed output is automatically edited and corrected. These all features concludes an Urdu parser with rich morphological, POS, syntactical and functional information in the form of a grammar in it. The parser with rich morphological information is comparable or better than the state-of-the-art in Urdu/Hindi domain. The evaluation results were compared with three parsers, which included the MPSRP for Urdu, a two stage constraint based dependency parser for Hindi and the simple Hindi dependency parser. The Urdu parser has better evaluation results as compared to these three parsers presented. It can help the linguists analyze the Urdu sentences computationally and can be useful in Urdu language processing and machine learning domains. By using this parser, the size of the treebank can also be increased. At present, the treebank contains only 1,400 annotated sentences, which can be increased. This can be done after getting the partial parsed trees of unknown sentences. These partial parsed trees can be corrected and then imported into the URDU.KON-TB treebank. The issues discussed about the handling of empty productions will be addressed further, when this parser will be shifted toward a statistical one.
Acknowledgements
I would like to thank Prof. Dr. Miriam Butt, University of Konstanz, Germany, who invested her full effort in guiding me to achieve this goal of parsing for morphologically rich language Urdu. Moreover, special thanks goes to unknown reviewers of this article because the quality and presentation of this article is sufficiently improved with their valuable comments, critics, suggestions and support.
