LL grammar
ઔપચારિક ભાષા સિદ્ધાંતમાં, એલ. એલ. વ્યાકરણ એ સંદર્ભ-મુક્ત વ્યાકરણ છે જેને એલ. એલ. પાર્સર દ્વારા પદચ્છેદન કરી શકાય છે, જે ઇનપુટને ડાબેથી જમણે પદચ્છેદન કરે છે, અને વાક્યની સૌથી ડાબી બાજુની વ્યુત્પત્તિ બનાવે છે (તેથી એલ. એલ., એલ. આર. પાર્સરની સરખામણીમાં જે સૌથી જમણી બાજુની વ્યુત્પત્તિ બનાવે છે). એલ. એલ. વ્યાકરણ ધરાવતી ભાષાને એલ. એલ. ભાષા તરીકે ઓળખવામાં આવે છે. આ અનુક્રમે નિર્ધારક સંદર્ભ-મુક્ત વ્યાકરણ (ડી. સી. એફ. જી.) અને નિર્ધારક સંદર્ભ-મુક્ત ભાષાઓ (ડી. સી. એફ. એલ.) ના ઉપગણ બનાવે છે. એક કહે છે કે આપેલ વ્યાકરણ અથવા ભાષા "એલ. એલ. વ્યાકરણ/ભાષા છે" અથવા ફક્ત "એલ. એલ. છે" તે સૂચવવા માટે કે તે આ વર્ગમાં છે. એલ. એલ. પાર્સર્સ ટેબલ-આધારિત પાર્સર્સ છે, જે એલ. આર. પાર્સર્સની જેમ જ છે. એલ. એલ. વ્યાકરણને વૈકલ્પિક રીતે ચોક્કસપણે તે તરીકે વર્ગીકૃત કરી શકાય છે જેને આગાહીયુક્ત પદચ્છેદન દ્વારા પદચ્છેદન કરી શકાય છે-બેકટ્રેકિંગ વિના પુનરાવર્તિત ઉતરતા પદચ્છેદન-અને આ સહેલાઈથી હાથથી લખી શકાય છે. આ લેખ એલ. એલ. વ્યાકરણના ઔપચારિક ગુણધર્મો વિશે છે; પદચ્છેદન માટે, એલ. એલ. પાર્સર અથવા રિકર્સિવ ડિસેન્ટ પાર્સર જુઓ. ઔપચારિક વ્યાખ્યા મર્યાદિત કેસ કુદરતી સંખ્યાને ધ્યાનમાં રાખીને, સંદર્ભ-મુક્ત વ્યાકરણ એ LL (k) વ્યાકરણ છે જો પ્રતીકો સુધીની લંબાઈના દરેક અંતિમ પ્રતીક શબ્દમાળા માટે, દરેક બિન-અંતિમ પ્રતીક માટે, અને દરેક અંતિમ પ્રતીક શબ્દમાળા માટે, વધુમાં વધુ એક ઉત્પાદન નિયમ હોય જેમ કે કેટલાક અંતિમ પ્રતીક શબ્દમાળાઓ માટે, શબ્દમાળા પ્રારંભિક પ્રતીકમાંથી મેળવી શકાય છે, પ્રથમ નિયમ લાગુ કર્યા પછી મેળવી શકાય છે, અને અને સંમત થવાના પ્રથમ પ્રતીકો. એક વૈકલ્પિક, પરંતુ સમકક્ષ, ઔપચારિક વ્યાખ્યા નીચે મુજબ છેઃ એક એલ. એલ. (કે) વ્યાકરણ છે જો, મનસ્વી વ્યુત્પત્તિઓ માટે જ્યારે પ્રથમ પ્રતીકો સાથે સંમત થાય છે. અનૌપચારિક રીતે, જ્યારે પાર્સર તેની ડાબી બાજુના નોન-ટર્મિનલ સાથે વ્યુત્પન્ન થાય છે અને પહેલેથી જ ઇનપુટમાંથી વપરાશ કરે છે, ત્યારે તેને જોઈને અને વર્તમાન ઇનપુટના આગામી પ્રતીકો પર ડોકિયું કરીને, પાર્સર નિશ્ચિતતા સાથે ઉત્પાદન નિયમને ઓળખી શકે છે. જ્યારે ભૂતકાળના ઇનપુટને ધ્યાનમાં લીધા વિના પણ નિયમની ઓળખ શક્ય હોય, ત્યારે વ્યાકરણને મજબૂત એલ. એલ. (કે) વ્યાકરણ કહેવામાં આવે છે. મજબૂત એલ. એલ. (કે) વ્યાકરણની ઔપચારિક વ્યાખ્યામાં, માટે સાર્વત્રિક પરિમાણને અવગણવામાં આવે છે, અને માટે "કેટલાક માટે" પરિમાણમાં ઉમેરવામાં આવે છે. દરેક એલ. એલ. (કે) વ્યાકરણ માટે માળખાકીય રીતે સમકક્ષ મજબૂત એલ. એલ. (કે) વ્યાકરણનું નિર્માણ કરી શકાય છે. એલ. એલ. (કે) ભાષાઓનો વર્ગ સમૂહોનો સખત રીતે વધતો ક્રમ બનાવે છેઃ એલ. એલ. (0) એલ. એલ. (1) એલ. એલ. (2). આપેલ વ્યાકરણ G એ LL (k) છે કે કેમ તે નિર્ણાયક છે, પરંતુ તે નક્કી કરી શકાતું નથી કે મનસ્વી વ્યાકરણ અમુક k માટે LL (k) છે કે કેમ. જો આપેલ LR (k) વ્યાકરણ પણ અમુક m માટે LL (m) વ્યાકરણ હોય તો તે પણ નિર્ણાયક છે. દરેક LL (k) વ્યાકરણ પણ LR (k) વ્યાકરણ છે. ε-મુક્ત LL (1) વ્યાકરણ પણ SLR (1) વ્યાકરણ છે. ખાલી અને ખાલી ન હોય તેવા બંને વ્યુત્પત્તિ ધરાવતા પ્રતીકો સાથેનું એલ. એલ. (1) વ્યાકરણ પણ એલ. એ. એલ. આર. (1) વ્યાકરણ છે. ખાલી વ્યુત્પત્તિ ધરાવતા પ્રતીકો સાથેનું એલ. એલ. (1) વ્યાકરણ એલ. એ. એલ. આર. (1) હોઈ શકે છે અથવા ન પણ હોઈ શકે. એલ. એલ. વ્યાકરણમાં ડાબું પુનરાવર્તન ધરાવતા નિયમો ન હોઈ શકે. દરેક એલ. એલ. (કે) વ્યાકરણ કે જે ε-મુક્ત હોય તેને ગ્રેબાચના સામાન્ય સ્વરૂપમાં સમકક્ષ એલ. એલ. (કે) વ્યાકરણમાં રૂપાંતરિત કરી શકાય છે (જે વ્યાખ્યા દ્વારા ડાબી પુનરાવર્તન સાથે નિયમો ધરાવતા નથી). રેગ્યુલર કેસ ચાલો અંતિમ મૂળાક્ષર હોઈએ. જો દરેક ભાષા નિયમિત હોય તો તેના પાર્ટીશનને નિયમિત પાર્ટીશન કહેવામાં આવે છે. ચાલો સંદર્ભ મુક્ત વ્યાકરણ બનીએ અને તેનું નિયમિત વિભાજન બનીએ. આપણે કહીએ છીએ કે તે LL () વ્યાકરણ છે જો, મનસ્વી વ્યુત્પત્તિઓ માટે જેમ કે તે તેને અનુસરે છે. વ્યાકરણ G ને LL-રેગ્યુલર (LLR) કહેવામાં આવે છે જો G એ LL () હોય તેવું નિયમિત પાર્ટીશન અસ્તિત્વમાં હોય. એક ભાષા એલ. એલ.-નિયમિત હોય છે જો તે એલ. એલ.-નિયમિત વ્યાકરણ દ્વારા ઉત્પન્ન થાય છે. એલ. એલ. આર. વ્યાકરણ અસંદિગ્ધ છે અને ડાબું-પુનરાવર્તિત ન હોઈ શકે. દરેક એલએલ (કે) વ્યાકરણ એલએલઆર છે. દરેક એલ. એલ. (કે) વ્યાકરણ નિર્ધારક છે, પરંતુ એક એલ. એલ. આર. વ્યાકરણ અસ્તિત્વમાં છે જે નિર્ધારક નથી. તેથી LLR વ્યાકરણનો વર્ગ દરેક k માટે LL (k) ના જોડાણ કરતાં સખત રીતે મોટો છે. નિયમિત પાર્ટીશન આપવામાં આવે તો, આપેલ વ્યાકરણ LL () છે કે કેમ તે નક્કી કરી શકાય છે. જો કે, તે નક્કી કરી શકાતું નથી કે મનસ્વી વ્યાકરણ G એ LLR છે કે નહીં. આ એ હકીકતને કારણે છે કે વ્યાકરણ G નિયમિત ભાષા ઉત્પન્ન કરે છે કે કેમ તે નક્કી કરવું, જે G માટે નિયમિત પાર્ટીશન શોધવા માટે જરૂરી હશે, તેને પોસ્ટ પત્રવ્યવહાર સમસ્યામાં ઘટાડી શકાય છે. દરેક એલએલઆર વ્યાકરણ એલઆર-રેગ્યુલર (એલઆરઆર, એલઆર (કે) વ્યાકરણ માટે સમકક્ષ) છે, પરંતુ એક એલઆર (1) વ્યાકરણ અસ્તિત્વમાં છે જે એલએલઆર નથી. ઐતિહાસિક રીતે, એલએલઆર વ્યાકરણ એલઆરઆર વ્યાકરણની શોધને અનુસરે છે. નિયમિત પાર્ટીશનને જોતાં, મૂરે મશીનને જમણેથી ડાબે પાર્સિંગને ટ્રાન્સડ્યુસ કરવા માટે બનાવી શકાય છે, જે નિયમિત ઉત્પાદનના ઉદાહરણોને ઓળખે છે. એકવાર તે થઈ ગયા પછી, એલ. એલ. (1) પાર્સર રેખીય સમયમાં ટ્રાન્સડ્યુસ્ડ ઇનપુટને હેન્ડલ કરવા માટે પૂરતું છે. આમ, એલએલઆર પાર્સર્સ એલએલ (કે) પાર્સર્સ કરતા સખત રીતે મોટા વ્યાકરણના વર્ગને સંભાળી શકે છે, જ્યારે તે સમાન રીતે કાર્યક્ષમ છે. તેમ છતાં એલ. એલ. આર. ના સિદ્ધાંતની કોઈ મોટી ઉપયોગિતા નથી. એક સંભવિત અને ખૂબ જ બુદ્ધિગમ્ય કારણ એ છે કે LL (k) અને LR (k) પાર્સર માટે જનરેટિવ એલ્ગોરિધમ્સ હોવા છતાં, LLR/LRR પાર્સર બનાવવાની સમસ્યા અનિશ્ચિત છે સિવાય કે કોઈએ નિયમિત પાર્ટીશન અગાઉથી બનાવ્યું હોય. પરંતુ વ્યાકરણને ધ્યાનમાં રાખીને યોગ્ય નિયમિત પાર્ટીશન બનાવવાની સમસ્યા પણ અનિશ્ચિત છે. સરળ નિર્ધારક ભાષાઓ સંદર્ભ-મુક્ત વ્યાકરણને સરળ નિર્ધારક અથવા માત્ર સરળ કહેવામાં આવે છે, જો તે ગ્રેબાચના સામાન્ય સ્વરૂપમાં હોય (એટલે કે. દરેક નિયમનું સ્વરૂપ હોય છે), અને સમાન નોન-ટર્મિનલ માટે જુદી જુદી જમણી બાજુઓ હંમેશા જુદી જુદી ટર્મિનલથી શરૂ થાય છે. જો તેમાં સરળ નિર્ધારક વ્યાકરણ હોય તો શબ્દમાળાઓના સમૂહને સરળ નિર્ધારક અથવા માત્ર સરળ ભાષા કહેવામાં આવે છે. ગ્રેબાચના સામાન્ય સ્વરૂપમાં ε-મુક્ત LL (1) વ્યાકરણ ધરાવતી ભાષાઓનો વર્ગ સરળ નિર્ધારક ભાષાઓના વર્ગ સમાન છે. આ ભાષાના વર્ગમાં ε ન ધરાવતા નિયમિત સમૂહોનો સમાવેશ થાય છે. સમાનતા તેના માટે નિર્ણાયક છે, જ્યારે સમાવેશ નથી. એપ્લિકેશન્સ એલ. એલ. વ્યાકરણ, ખાસ કરીને એલ. એલ. (1) વ્યાકરણ, ખૂબ વ્યવહારુ રસ ધરાવે છે, કારણ કે તેઓ એલ. એલ. પાર્સર્સ દ્વારા અથવા રિકર્સિવ ડિસેન્ટ પાર્સર્સ દ્વારા વિશ્લેષણ કરવા માટે સરળ છે, અને આ કારણોસર એલ. એલ. (1) તરીકે ડિઝાઇન કરવામાં આવ્યા છે. k ના ઊંચા મૂલ્યવાળા વ્યાકરણ પર આધારિત ભાષાઓને પરંપરાગત રીતે વિશ્લેષણ કરવું મુશ્કેલ માનવામાં આવે છે, જો કે મનસ્વી k માટે LL (k) વ્યાકરણને ટેકો આપતા પાર્સર જનરેટરની ઉપલબ્ધતા અને વ્યાપક ઉપયોગને ધ્યાનમાં રાખીને હવે આ ઓછું સાચું છે. LL (k) અને LL (*) પાર્સરની યાદી માટે પાર્સર જનરેટરની સરખામણી પણ જુઓ.